Chapter 5.4, Problem 24ES

Imagine a situation in which eight people, numbered consecutively 1—8, are arranged in a circle. Starting from person #1, every second person in the circle is eliminated. The elimination process continues until only one person remains. In the first round the people numbered 2, 4, 6, and 3 are eliminated, in the second round the people numbered 3 and 7 are eliminated, and in the third round person #5 is eliminated, so after the third round only person #1 remains, as shown on the next page.

a. Given a set of sixteen people arranged in a circle and numbered, consecutively 1—16, list the numbers of the people who are eliminated in each round if every second person is eliminated and the elimination process continues until only one person remains. Assume that the starting point is person #1.
b. Use ordinary mathematical induction to prove that for every integer $n\ge 1$ , given any set of $2^n$ people arranged in a circle and numbered consecutively 1 through $2^n$ , if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #1 will remain.

c. Use the result of part (b) to prove that for any nonnegative integers n and m with $2^n\le 2^n+m<2^{n+1}$ , if $r=2^n+m$ , then given any set of r people arranged in a circle and numbered consecutively 1 through r, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person $\#\left(2m+1\right)$ will remain.