Question

The numbers $1, 2, \dots, n$ are written in natural order. Numbers in odd places are struck off to form a new sequence. This process is continued until only one number is left. If $n = 1997$, find the last remaining number.

• A. 1996
• B. 1988
• C. 512
• D. 1024

Hint:

For repeated elimination of odd positions, the last remaining number is always the largest power of 2 less than or equal to $n$.

Answer 1

The Correct Option is D

To solve the problem of finding the last remaining number when repeatedly striking out the numbers in odd positions from the sequence \(1, 2, \ldots, n\) until a single number remains, observe the pattern:

1. Begin with the sequence \(1, 2, \ldots, 1997\).

2. On each iteration, numbers in odd positions are removed. Initially, the odd positions contain numbers \(1, 3, 5, \ldots, 1997\).

3. After removing odd-positioned numbers, the sequence becomes all numbers previously in even positions: \(2, 4, 6, \ldots, 1996\).

4. The task repeats: remove numbers in odd positions from the new sequence. This doubles the step sizes.

The sequence structure of striking odd positions mirrors halving the range, retaining powers of 2.

5. With each step, the starting point and range reduce consistently, leaving the largest power of 2 in original collection.

Find largest power of 2 ≤ 1997:

\(2^0 = 1, 2^1 = 2, 2^2 = 4, \ldots, 2^{10} = 1024\)

The largest power of 2 within \(1997\) is \(2^{10} = 1024\).

Hence, the last remaining number is 1024.