Track / Stage 5 / 386 of 400 #986 of 1964

Problem 986

AIME late

Combinatorics Difficulty 6.0 Prove it

3. There are three piles of stones on the table, with numbers $100$ , $101$ , and $102$ respectively. Two people, A and B, take turns to perform the following operation: each person can take stones from any pile in the first step, starting with A, and in each step, one of them takes one stone from a pile, but cannot take from the pile they took stones from in their previous turn. The one who cannot make a move loses. Question: Regardless of how the opponent operates, who has a sure-win strategy?

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

3. Player A has a winning strategy.

Let the piles that initially contain $100$ , $101$ , and $102$ stones be denoted as $A$ , $B$ , and $C$ respectively.

Player A first takes one stone from pile $B$ , making the number of stones in the three piles $100$ , $100$ , and $102$ , all of which are even.
(1) If Player B does not take from pile $B$ , then Player A will always take from the same pile as Player B. Since the number of stones in each pile is even after Player A's turn, and as long as Player B does not take from the pile they took from in the previous round, Player A will not take from the pile they took from in the previous round. Therefore, Player A can always make a move after Player B. Since the game will eventually end, Player A will win.
(2) If Player B takes from pile $B$ , then Player A will follow these rules:
- If Player B takes from pile $B$ , Player A will take from pile $A$ ;
- If Player B takes from pile $A$ , Player A will take from pile $B$ ;
- If Player B takes from pile $C$ , Player A will take from pile $C$ .
Thus, after Player A's turn, pile $C$ will always have an even number of stones, and the number of stones in piles $A$ and $B$ will always be equal. Therefore, as long as Player B does not take from the pile they took from in the previous round, Player A will not take from the pile they took from in the previous round. Thus, Player A can always make a move after Player B. Since the game will eventually end, Player A will win.
In conclusion, Player A has a winning strategy.

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