Maths Olympiad Prep

Library / /33 of 42

Combinatorics Difficulty 6.5 National olympiad Prove it Ireland

At the start of a game, a positive integer MM is fixed and you are given boxes BiB_i for each iNi \in \mathbb{N}, all are empty. You can adjust the number of marbles in the boxes by making a series of moves. The allowable moves are as follows:
Move A: Add a marble to B1B_1 and to B2B_2.
Move B: Add a marble to B1B_1 and to BMB_M.
Move C_k: Take two marbles from BkB_k for some kk and add a marble to Bk+1B_{k+1}.
Moves can be repeated if you wish. You can do a move of the form CkC_k for any desired values of kk, as long as Box BkB_k contains at least two marbles.
You win the game if you reach a stage where one box has a single marble and all other boxes are empty.
Since the game depends on the number MM, we call it the MM-game. As an example, the following sequence of moves allows you to win the 3-game. We also give the number of marbles in the first few boxes after each listed move; later boxes are all empty.
```
A: 1 1
B: 2 1 1
C₁: 0 2 1
C₂: 0 0 2
C₃: 0 0 0 1 (winning position)
```
For which values of MNM \in \mathbb{N} is it possible to win the MM-game? Explain carefully for each MM how you can win or why you can't win.

Solution

We denote by mi,jm_{i,j} the number of marbles in Box BiB_i after jj moves, and we define the associated sum sjs_j by
sj:=i=1mi,j2i1. s_j := \sum_{i=1}^{\infty} m_{i,j} 2^{i-1}.
We have s0=0s_0 = 0 and each sjsj1s_j - s_{j-1} is non-negative. In fact, sjsj1s_j - s_{j-1} equals:
31+2M10}if the j’th move isABCk}(11) \left. \begin{array}{c} 3 \\ 1+2^{M-1} \\ 0 \end{array} \right\} \quad \text{if the } j\text{'th move is} \quad \left. \begin{array}{c} A \\ B \\ C_k \end{array} \right\} \qquad (11)
It follows that sj>1s_j > 1 for all j>0j > 0, and that a necessary condition to win after jj steps is that sjs_j is a power of 2.
Suppose MM is even. Then, 1+2M11+2^{M-1} is a multiple of 3, so it follows inductively from (11) that sjs_j is divisible by 3 for all jj. We deduce that sjs_j is never a power of 2. Thus, we cannot win the MM-game if MM is even.
Suppose instead that MM is odd. Then 1+2M12(mod3)1 + 2^{M-1} \equiv 2 \pmod 3. If we first do Move BB and then repeatedly do Move AA, the numbers sjs_j take on all values vv0:=1+2M1v \ge v_0 := 1 + 2^{M-1} that are congruent to 2 (mod 3). We eventually reach a power of 2; in fact, using these moves, sjs_j hits each odd power of 2 exceeding v0v_0.
Suppose that
sj=i=1mi,j2i1 s_j = \sum_{i=1}^{\infty} m_{i,j} 2^{i-1}
equals 2P2^P for some PNP \in \mathbb{N}. All our subsequent moves will be CC-moves (meaning moves of the form CkC_k) and we continue until we can no longer perform a CC-move. Each CC-move lowers the total number of marbles by 1, so eventually no further CC-moves are possible. Note though that the sum stays unchanged according to (11), so it is still 2P2^P.
Suppose that after JjJ \ge j steps, we can go no further. This implies that mi,J1m_{i,J} \le 1 for all ii. Let NN be the largest value of ii such that mi,J=1m_{i,J} = 1, and suppose we are not in a winning position i.e. mi,J=1m_{i,J} = 1 for at least one value of i<Ni < N. Then
2N1<sJ=i=1Nmi,J2i1i=1N2i1=2N1. 2^{N-1} < s_J = \sum_{i=1}^{N} m_{i,J} 2^{i-1} \le \sum_{i=1}^{N} 2^{i-1} = 2^N - 1.
This contradicts the assumption that sJs_J is a power of 2. We conclude that the sequence of CC-moves can end only when we reach a winning position.
We have shown that we can win if and only if MM is odd, and we have an algorithm for winning when it is possible.

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 and solution reproduced as published; topic and difficulty added by this site.