Maths Olympiad Prep

Track / Stage 6 / 188 of 400 #1188 of 1964

Problem 1188

National olympiad, first round
Combinatorics Difficulty 6.3 Find the answer

A pack of 20082008 cards, numbered from 11 to 20082008, is shuffled in order to play a game in which each move has two steps:

(i) the top card is placed at the bottom;

(ii) the new top card is removed.

It turns out that the cards are removed in the order 1,2,,20081,2,\dots,2008. Which card was at the top before the game started?

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

To solve this problem, we need to understand the sequence of operations and how they affect the position of the cards. Let's denote the initial position of the cards as a1,a2,,a2008a_1, a_2, \ldots, a_{2008}, where aia_i represents the card with number ii.

1. Understanding the Operations:
- Step (i): The top card is placed at the bottom.
- Step (ii): The new top card is removed.

2. Simulating the Process:
- Initially, the cards are in the order 1,2,3,,20081, 2, 3, \ldots, 2008.
- After the first move, the card 11 is placed at the bottom, and card 22 is removed.
- After the second move, the card 33 is placed at the bottom, and card 44 is removed.
- This process continues until all cards are removed.

3. Pattern Recognition:
- We need to determine the initial position of the card that ends up being removed last, which is card 20082008.
- Notice that the sequence of removals follows a specific pattern. The card that is removed in the nn-th position is the card that was initially in the 2n12n-1-th position.

4. General Formula:
- For n=2mkn = 2^m k where kk is odd, the card that ends up in the nn-th position is given by nk12n - \frac{k-1}{2}.

5. Applying the Formula:
- For n=2008n = 2008, we need to express 20082008 in the form 2mk2^m k.
- 2008=232512008 = 2^3 \cdot 251, where 251251 is odd.
- Using the formula, the initial position of the card that ends up being removed last is:
200825112=2008125=1883 2008 - \frac{251-1}{2} = 2008 - 125 = 1883

Therefore, the card that was at the top before the game started is card number 18831883.

The final answer is 1883\boxed{1883}.

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