Maths Olympiad Prep

Library / IRL ABooklet /173 of 191

IRL ABooklet

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Ireland

A game of coins is played as follows: You start with 11 head and 11 tail on a table. At each turn, you can perform any one of the following moves:

a. You can turn over all the coins on the table.

b. You can triple the numbers of heads and tails on the table.

c. If there are at least 44 tails on the table, you can turn over 44 tails.

d. If there are at least 55 tails on the table, you can turn over 33 of the tails and discard 22 of the tails.

Knowing that at the end of a game you have 20242024 heads, what are the possible numbers of tails at the end of that game?

Solution

Let xx be the number of heads and yy the number of tails at each point of the game. The pair (x,y)(x, y) completely describes the state of the game. Let D(x,y)=x−yD(x, y) = x - y. This quantity behaves as follows under each possible move:

a. (x,y)→(y,x)(x, y) \to (y, x) changes D(x,y)D(x, y) to −D(x,y)-D(x, y).

b. (x,y)→(3x,3y)(x, y) \to (3x, 3y) changes D(x,y)D(x, y) to 3D(x,y)3D(x, y).

c. If y≥4y \ge 4, move (x,y)→(x+4,y−4)(x, y) \to (x + 4, y - 4) changes D(x,y)D(x, y) to D(x,y)+8D(x, y) + 8.

d. If y≥5y \ge 5, move (x,y)→(x+3,y−5)(x, y) \to (x + 3, y - 5) changes D(x,y)D(x, y) to D(x,y)+8D(x, y) + 8.

We will indicate composition of moves using the symbol ∘\circ so that, for example, (b)∘\circ(a) is the move (a) followed by move (b), which sends (x,y)(x, y) to (3y,3x)(3y, 3x), and (b)m(b)^m is the mm-fold composition of (b) sending (x,y)(x, y) to (3mx,3my)(3^m x, 3^m y). We introduce the following moves:
(c′)=(a)∘(c)∘(a): If x≥4, it sends (x,y) to (x−4,y+4). (c') = (a) \circ (c) \circ (a): \text{ If } x \ge 4, \text{ it sends } (x, y) \text{ to } (x - 4, y + 4).
(d′)=(a)∘(d)∘(a): If x≥5, it sends (x,y) to (x−3,y+5). (d') = (a) \circ (d) \circ (a): \text{ If } x \ge 5, \text{ it sends } (x, y) \text{ to } (x - 3, y + 5).
We also define a move (e) which sends (x,y)(x, y) to (x−1,y−1)(x - 1, y - 1) if xx and yy are both positive and one of them is at least 44:
(e)={(d′)∘(c)if x≥1,y≥4(d)∘(c′)if x≥4,y≥1. (e) = \begin{cases} (d') \circ (c) & \text{if } x \ge 1, y \ge 4 \\ (d) \circ (c') & \text{if } x \ge 4, y \ge 1. \end{cases}
Finally, we define moves (f) and (f') as follows:
(f)=(c)∘(e)4: If x≥4 and y≥8, it sends (x,y) to (x,y−8). (f) = (c) \circ (e)^4: \text{ If } x \ge 4 \text{ and } y \ge 8, \text{ it sends } (x, y) \text{ to } (x, y - 8).
(f′)=(c′)∘(e)4: If x≥8 and y≥4, it sends (x,y) to (x−8,y). (f') = (c') \circ (e)^4: \text{ If } x \ge 8 \text{ and } y \ge 4, \text{ it sends } (x, y) \text{ to } (x - 8, y).
To prove that each pair (2024,8n)(2024, 8n) with n≥0n \ge 0 can be reached during the game, we first apply move (b) kk times, where 3k≥a3^k \ge a, and then move (e) a number of times to get
(1,1)→(3,3)→(9,9)→⋯→(3k,3k)→(3k−1,3k−1)→⋯→(a,a). (1, 1) \to (3, 3) \to (9, 9) \to \dots \to (3^k, 3^k) \to (3^k - 1, 3^k - 1) \to \dots \to (a, a).
This shows that we can get any pair (a,a)(a, a) with a≥3a \ge 3. In particular, we can get any pair (8n,8n)(8n, 8n) with n≥1n \ge 1. If 8n≥2024=8⋅2538n \ge 2024 = 8 \cdot 253 we apply move (f′)(f') a number of times to reach (2024,8n)(2024, 8n) for any n≥253n \ge 253. To reach (2024,8n)(2024, 8n) for 0≤n<2530 \le n < 253, we start with (2024,2024)(2024, 2024) and apply move (f) a suitable number of times. Hence, for any n≥0n \ge 0 we can reach (2024,8n)(2024, 8n) from (1,1)(1, 1) after a finite number of moves.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.