Library / IMO 2J, Independent Study 2 /1 of 2

IMO 2J, Independent Study 2

Combinatorics Difficulty 8.7 Shortlist Prove it Taiwan

Let $k$ be a positive integer. The little one and the magician on the skywalk play a game. Initially, the little one places $N = 2^k$ distinct balls in a row on the table, and covers each of them by a cup. On each turn, the little one chooses two cups, then the magician can either swap the balls in the two cups, or do a fake move so that the balls in the two cups stay the same. The little one cannot distinguish whether the magician fakes a move on not, nor can she observe the balls inside the cups.
After $M = k \times 2^{k-1}$ turns, the magician opens all cups so the little one can check the ball in each of the cups. If the little one can identify whether the magician fakes a move or not for each of the $M$ turns, then the little one wins. Prove that the little one has a winning strategy.

Solution

Number all the cups from 1 to $N$ in order. We will construct the strategy by induction. The case $k=1$ is obvious. Now suppose that for $k-1$ there exists a winning strategy which, on turns $i=1,2,\dots,(k-1)2^{k-2}$ , chooses the cups numbered $a_i$ and $b_i$ . Then for $k$ , let $M_1 = 2^{k-1}$ and $M_2 = (k+1)2^{k-2}$ , and consider the following strategy:

Stage 1: On turns $i = 1,2,\dots,M_1$ , choose the cups numbered $i$ and $i + M_1$
(note that $i + M_1 \le 2M_1 = 2^k$ );

Stage 2: On turns $i = M_1 + 1, \dots, M_2$ , choose the cups numbered $a_{i-M_1}$ and $b_{i-M_1}$
(note that $i - M_1 \le M_2 - M_1 = (k-1)2^{k-2}$ );

Stage 3: On turns $i = M_2 + 1, \dots, M$ , choose the cups numbered $a_{i-M_2} + 2^{k-1}$ and $b_{i-M_2} + 2^{k-1}$
(note that $i - M_2 \le M - M_2 = (k-1)2^{k-2}$ ).

We now prove that this is indeed a winning strategy. Let $X$ denote the cups numbered 1 through $M_1$ , and let $Y$ denote the cups numbered $M_1+1$ through $N$ .
- First, note that only during Stage 1 can a ball in $X$ and a ball in $Y$ possibly be exchanged, and only the operation on turn $i$ can possibly move ball $i$ from $X$ to $Y$ . Therefore, for every $i$ in Stage 1, we know that turn $i$ is a fake move if and only if ball number $i$ still remains in region $X$ at the end.
- Note that Stage 2 amounts to carrying out the winning strategy for $k-1$ on $X$ , and we already know the full distribution of balls in region $X$ at the end of Stage 1; therefore, by the induction hypothesis, we can determine whether any given turn in Stage 2 was a fake move by observing the final distribution of balls in region $X$ .
- Similarly, Stage 3 amounts to carrying out the winning strategy for $k-1$ on $Y$ , and we already know the full distribution of balls in region $Y$ at the end of Stage 1; therefore, by the induction hypothesis, we can determine whether any given turn in Stage 3 was a fake move by observing the final distribution of balls in region $Y$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.