Imagine a situation in which eight people, numbered consecutively 18, are arranged in a

Chapter 5, Problem 25

(choose chapter or problem)

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 8 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 below.

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 mathematical induction to prove that for all integers n ≥ 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} ≤ 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 #(2m + 1) will remain.

Text Transcription:

2^n

2^n ≤ 2^n + m < 2^n+1

r = 2^n + m