Maths Olympiad Prep

Library / /11 of 13

Combinatorics Difficulty 6.8 National olympiad Find the answer

The integer numbers from 11 to 20022002 are written in a blackboard in increasing order 1,2,,2001,20021,2,\ldots, 2001,2002. After that, somebody erases the numbers in the (3k+1)th (3k+1)-th places i.e. (1,4,7,)(1,4,7,\dots). After that, the same person erases the numbers in the (3k+1)th(3k+1)-th positions of the new list (in this case, 2,5,9,2,5,9,\ldots). This process is repeated until one number remains. What is this number?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let's analyze the process of elimination step by step, starting from the list of integers from 1 to 2002:

### Step 1:
Initially, the numbers 1,2,,20021, 2, \ldots, 2002 are written on the board. In this first step, numbers at positions 1,4,7,1, 4, 7, \ldots (i.e., (3k+1) (3k+1) -th positions for k=0,1,2,k = 0, 1, 2, \ldots) are erased.

These positions correspond to the arithmetic sequence:
3k+1(k=0,1,2,) 3k + 1 \quad (k = 0, 1, 2, \ldots)

### Step 2:
After the first round of erasure, the sequence is reduced, starting from 2 with a common difference of 3:
2,3,5,6,8,9, 2, 3, 5, 6, 8, 9, \ldots

Now, we erase numbers again at the positions (3k+1) (3k+1) -th of the new sequence, specifically items such as 2, 5, 8, \ldots

### Subsequent Steps:
This process continues iteratively. After each round of erasure, we get a new list of numbers. The sequence of positions 3k+13k + 1 will become sparser, and the number of remaining numbers will decrease.

### Key Observation:
Because we have to erase at positions 3k+13k+1 continually and remove the numbers in those positions, and given the dense initial set from 1 to 2002, every remaining number after a complete iteration follows the form 2,6,10,2, 6, 10, \ldots, which translates to:

2+4n(n=0,1,2,) 2 + 4n \quad (n = 0, 1, 2, \ldots)

Each sequence formed here is 4 positions apart.

### Final Step:
This removal efficiently sequences down the integers until only one number remains. The pattern observed means the result can only be consistent with the arithmetic progression defined by terms like 2,6,10,2, 6, 10, \ldots.

### Conclusion:
As such numbers maintain their presence down every possible iteration due to the arithmetic progression nature and group nature (distance multiplying by a factor each time), these terms remain consistent choices. Since after enough eliminations these sequences essentially divide down until a single sequence element sustains:

Thus, the number remaining is:
2,6,10 \boxed{2,6,10}
This step-based approach confirms that numbers fitting this gap are never fully eliminated in any active 3k+13k+1 sequence defined reductions, but maintaining membership in all-remaining 2,6,10,2,6,10,\ldots ones.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.