Maths Olympiad Prep

Library / /441 of 462

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Ireland

Alice and Brian play a game. Before they start, Alice chooses a positive integer nn and Brian then chooses the initial value of another positive integer mm. They then place nn counters on a board and take turns removing them; Alice always moves first.
Each move, for some player PP, always has two parts:
(a) PP either lets mm unchanged or reduces its value by 11, with the exception that if m=1m = 1, then mm cannot be changed.
(b) PP then removes mm counters from the board.
Eventually, there are too few counters left for PP to do (b) and PP loses. The winner depends on nn, the initial mm, and the moves made. For instance, suppose n=11n = 11 and initially m=5m = 5. Alice should first remove 44 counters. Brian then removes either 44 or 33 counters, after which Alice should remove 33 counters. With at most one counter now on the table, Brian has no valid move so Alice wins. If instead, Alice initially removed 55 counters, it is easily verified that Alice is doomed to lose.

Alice and Brian agree to constrain nn and the initial mm: Alice must choose n2024n \ge 2024, and Brian is only allowed to choose m=2,m=3m = 2, m = 3, or m=4m = 4. Find the smallest nn that Alice can choose to guarantee her a win if she makes the right moves, regardless of Brian's choice of mm and his moves.

Solution

We will first define a function f:N×Z0{0,1}f: \mathbb{N} \times \mathbb{Z}_{\ge 0} \to \{0, 1\}, where Z0\mathbb{Z}_{\ge 0} indicates the non-negative integers, and then show that if the current player is faced with a particular pair of values (m,n)(m, n) then that player has a guaranteed win if f(m,n)=1f(m, n) = 1 but a guaranteed loss if f(m,n)=0f(m, n) = 0, both under the assumption that the winner makes the right moves. The definition will also indicate a winning strategy in all cases.

In our definition of ff, we implicitly assume that m,nm, n are integers with m>0m > 0 and n0n \ge 0 whenever we define f(m,n)f(m, n). We first define f(m,n)f(m, n) for m=1m = 1:
f(1,n):={0,n even,1,n odd.(7) f(1, n) := \begin{cases} 0, & n \text{ even,} \\ 1, & n \text{ odd.} \end{cases} \qquad (7)
We next define f(m,n)f(m, n) for m>1m > 1 and nmn \le m:
f(m,n):={0,n<m1,1,m1nm.(8) f(m, n) := \begin{cases} 0, & n < m - 1, \\ 1, & m - 1 \le n \le m. \end{cases} \qquad (8)
We call the values of ff defined above the *initial values of ff*. The remaining values f(m,n)f(m, n) are defined iteratively as follows, where we implicitly assume that n>m>1n > m > 1.
f(m,n):={0,if f(k,nk)=1 for k=m and k=m11,otherwise.(9) f(m, n) := \begin{cases} 0, & \text{if } f(k, n-k) = 1 \text{ for } k = m \text{ and } k = m-1 \\ 1, & \text{otherwise.} \end{cases} \qquad (9)
We claim that the above partial definitions give a consistent definition of ff on its full domain. First note that (7), (8), and (9) apply to non-overlapping sets of values (n,m)(n, m), so they are clearly consistent with each other, and it is similarly clear that each is internally consistent.
It remains to check that they provide a consistent definition f(m,n)f(m, n) for each allowable m,nm, n. This is clear for m=1m = 1 and for nmn \le m, so suppose n>m>1n > m > 1. Assume that f(i,j)f(i, j) is already consistently defined if either i<mi < m or i=mi = m and j<nj < n. Equation (9) then defines f(m,n)f(m, n) in terms of f(m,nm)f(m, n-m) and f(m1,nm+1)f(m-1, n-m+1). Thus, the definition is extended consistently to f(m,n)f(m, n). By induction on nn, we have defined f(m,n)f(m, n) for all nZ0n \in \mathbb{Z}_{\ge 0}, and now by induction on mm, we have defined f(m,n)f(m, n) for all allowable values of (m,n)(m, n). Next, we show that ff has the desired interpretation. First, (7) reflects the fact that with m=1m = 1, the game is predetermined because there is no choice: players take turns removing one counter after another and parity shows that the winner corresponds to the values of f(1,n)f(1, n).

Finally, we show inductively that (9) correctly indicates the winner in the remaining cases. Assuming that f(i,j)f(i, j) correctly indicates the winner both for i<mi < m and for i=mi = m when j<nj < n, then f(k,nk)=1f(k, n-k) = 1 for k{m,m1}k \in \{m, m-1\} indicates that both of these are winning positions so, faced with initial parameters (m,n)(m, n), the current player is forced to hand a winning position to the opponent.

On the other hand, if f(k,nk)=0f(k, n - k) = 0 for some k{m,m1}k \in \{m, m - 1\}, then the player can remove kk counters to hand a losing position to the other player. (If both values are 0, then either move works.) We have shown that the values of f(m,n)f(m, n) indicate the winner and provide a winning strategy.

Let us note two implications that follow from (9) and which we will use repeatedly:
f(m,nm)=1f(m,n)=1f(m1,nm+1),f(m1,nm+1)=1f(m,n)=1f(m,nm). \begin{aligned} f(m, n - m) &= 1 &\Rightarrow f(m, n) &= 1 - f(m - 1, n - m + 1), \\ f(m - 1, n - m + 1) &= 1 &\Rightarrow f(m, n) &= 1 - f(m, n - m). \end{aligned}
Let us show that
f(2,n)={0,n divisible by 4,1,otherwise.(10) f(2, n) = \begin{cases} 0, & n \text{ divisible by } 4, \\ 1, & \text{otherwise.} \end{cases} \qquad (10)
In fact, if nn is odd, then f(2,n)=1f(2, n) = 1 because f(1,n1)=0f(1, n - 1) = 0 by (7). If n>0n > 0 is even, then f(1,n1)=1f(1, n - 1) = 1, so f(2,n)=1f(2,n2)f(2, n) = 1 - f(2, n - 2). In view of the initial values f(2,0)=0f(2, 0) = 0 and f(2,2)=1f(2, 2) = 1, we get the desired values of ff. We next show that
f(3,n)={1,n=3 or (n>0 and n even),0,otherwise.(11) f(3, n) = \begin{cases} 1, & n = 3 \text{ or } (n > 0 \text{ and } n \text{ even}), \\ 0, & \text{otherwise.} \end{cases} \qquad (11)
The initial values give us (11) for n3n \le 3, so we suppose inductively that the equation in (11) holds as long as n<4kn < 4k for some kNk \in \mathbb{N}. Since f(2,4k)=0f(2, 4k) = 0, we have f(3,4k+2)=1f(3, 4k + 2) = 1. As for f(3,n)f(3, n) for n{4k,4k+1,4k+3}n \in \{4k, 4k + 1, 4k + 3\}, in each of these cases f(2,n2)=1f(2, n - 2) = 1 and so f(3,n)=1f(3,n3)f(3, n) = 1 - f(3, n - 3).
For n=4kn = 4k, we inductively have f(3,n3)=f(3,4n3)=0f(3, n - 3) = f(3, 4n - 3) = 0, so f(3,4k)=10=1f(3, 4k) = 1 - 0 = 1. This in turn implies that f(3,4k+3)=11=0f(3, 4k + 3) = 1 - 1 = 0. Similarly, f(3,4k+13)=1f(3, 4k + 1 - 3) = 1, so f(3,4k+1)=11=0f(3, 4k + 1) = 1 - 1 = 0. This completes the inductive step (from n<4kn < 4k to n<4(k+1)n < 4(k + 1)), so (11) is fully valid.
We next show that
f(4,n)={0,n<3 or n±1(mod8),1,otherwise.(12) f(4, n) = \begin{cases} 0, & n < 3 \text{ or } n \equiv \pm 1 \pmod 8, \\ 1, & \text{otherwise.} \end{cases} \qquad (12)
The initial values give us (12) for n4n \le 4, so we suppose that n>4n > 4. We get f(4,6)=1f(4, 6) = 1 because f(4,2)=0f(4, 2) = 0. For even n>6n > 6, we get f(4,n)=1f(4, n) = 1 because f(3,n3)=0f(3, n - 3) = 0.

Suppose therefore that n>4n > 4 is odd. Since f(3,n3)=1f(3, n-3) = 1, we have f(4,n)=1f(4,n4)f(4, n) = 1 - f(4, n-4). This equation plus the above initial values give us f(4,k)f(4, k) for all odd k>4k > 4.

We now have useful formulae for f(m,n)f(m, n) for all 1m41 \le m \le 4 and n0n \ge 0. For Alice to have a guaranteed win, she must choose the value of n2024n \ge 2024 so that f(m,n)=1f(m, n) = 1 for each m{2,3,4}m \in \{2, 3, 4\}. By our above formulae, m=2m = 2 rules out n=2024n = 2024, while m=3m = 3 rules out n=2025n = 2025. However, n=2026n = 2026 has the desired properties, so that is our answer. More generally, for n>3n > 3 we can say that f(2,n)=f(3,n)=f(4,n)=1(mod4)f(2, n) = f(3, n) = f(4, n) = 1 \pmod{4}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.