Track / Stage 8 / 124 of 180 #1824 of 1964

Problem 1824

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.6 Prove it IMO Problem Shortlist · IMO

Consider $2009$ cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins.

a. Does the game necessarily end?

b. Does there exist a winning strategy for the starting player?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

a.
We interpret a card showing black as the digit $0$ and a card showing gold as the digit $1$ . Thus each position of the $2009$ cards, read from left to right, corresponds bijectively to a nonnegative integer written in binary notation of $2009$ digits, where leading zeros are allowed. Each move decreases this integer, so the game must end.

b.
We show that there is no winning strategy for the starting player. We label the cards from right to left by $1, \ldots, 2009$ and consider the set $S$ of cards with labels $50i$ , $i=1,2, \ldots, 40$ . Let $g_{n}$ be the number of cards from $S$ showing gold after $n$ moves. Obviously, $g_{0}=40$ . Moreover, $|g_{n}-g_{n+1}|=1$ as long as the play goes on. Thus, after an odd number of moves, the nonstarting player finds a card from $S$ showing gold and hence can make a move. Consequently, this player always wins.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.