Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Italy

Problem:

Alberto and Barbara play the following game: initially there are some piles of tokens on a table (the number of tokens can vary from pile to pile). In turn, starting with Alberto, one of the two players makes one and only one of the following moves:
- either removes a token from a pile of their choice and eliminates it from the game;
- or splits a pile into two smaller piles, each with at least one token (without adding or removing tokens from the table).
The winner is whoever removes the last token from the table. Determine, depending on the number of piles present on the table at the start and how many tokens they contain, which of the two players has a winning strategy.

Solutions — 2

Solution 1

Solution:

Let us first assume that we start from a situation in which there is at least one token present on the table, otherwise the game cannot even begin.
Let C0,C1,C2,C_{0}, C_{1}, C_{2}, \ldots be the combinations of piles present at the start of the game, after the first move, after the second move, and so on. For each combination CiC_{i} let rir_{i} be the number of piles that have a number of tokens a1,a2,,aria_{1}, a_{2}, \ldots, a_{r_{i}} greater than 1 and sis_{i} the number of piles that have one token. Let then mi=(a11)++(ari1)m_{i}=\left(a_{1}-1\right)+\cdots+\left(a_{r_{i}}-1\right). We show that Barbara has a winning strategy if m0m_{0} and s0s_{0} are both even and that Alberto has a winning strategy in all other cases. The winning strategy is to leave the opponent, at each move, a combination CiC_{i} such that mim_{i} and sis_{i} are both even.

Indeed, observe that if a player is facing a combination in which mim_{i} and sis_{i} are both even, every move they make must lead to a combination in which at least one of mi+1m_{i+1} and si+1s_{i+1} is odd. Conversely, suppose a player is facing a combination in which mim_{i} and sis_{i} are not both even:
- if mim_{i} is even and sis_{i} is odd, they can remove a pile with 1 token;
- if mim_{i} is odd and sis_{i} is even, they can remove a token from a pile with at least 3 tokens (if one exists), or split a pile with 2 tokens into two piles with one token;
- if mim_{i} and sis_{i} are both odd, they can split a pile with a3a \geq 3 tokens (if one exists) into two piles with a1a-1 and 1 token, or they can remove a token from a pile containing 2.

In all cases, the player manages to produce again a combination in which mi+1m_{i+1} and si+1s_{i+1} are both even.

Since during the game the number of tokens present on the table can be left unchanged at most m0m_{0} times, the game certainly ends, and clearly the victory will go to whoever manages to propose the combination CnC_{n} in which mn=sn=0m_{n}=s_{n}=0, both even.

Solution 2

Solution:

Let sis_{i} be the number of piles with a single token and mim_{i} the number of piles with an even number of tokens. Also with this definition Barbara has a winning strategy if and only if s0s_{0} and m0m_{0} are even, and the winning strategy consists in always leaving the opponent a configuration in which sis_{i} and mim_{i} are even. Indeed if a player is facing a combination in which sis_{i} and mim_{i} are even, every move they make leads to a combination in which at least one of si+1s_{i+1} and mi+1m_{i+1} is odd. Conversely, if a player is facing a combination in which sis_{i} and mim_{i} are not both even, by moving as indicated above they manage to produce again a configuration in which si+1s_{i+1} and mi+1m_{i+1} are both even.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.