Maths Olympiad Prep

Library / /383 of 462

Combinatorics Difficulty 6.8 National Olympiad Prove it Ireland

Two players, Abigail and Zoe, play a game. Abigail chooses an odd number less than 800800 and writes it on the blackboard. Zoe now chooses a different odd number less than 12001200 and writes it on the blackboard. Each in turn replaces their number by the difference between their number and the smallest power of 22 bigger than their number. If both players reach 11 on the same move the game is drawn. If not, the player who first reaches 11 loses.
Who has the winning strategy?

Solution

Let nn be the current number of one of the players. Because both players start with an odd number, nn will be odd as it remains positive throughout the game. If n=i=0kbi2in = \sum_{i=0}^{k} b_i 2^i with bi{0,1}b_i \in \{0, 1\} is the binary representation of nn, then b0=1b_0 = 1. If we assume bk=1b_k = 1, then the smallest power of 22 that is bigger than nn is 2k+12^{k+1}, hence, the next number for this player will be
2k+1n=1+i=0k2ii=0kbi2i=1+i=0k(1bi)2i=i=0k1ci2i, 2^{k+1} - n = 1 + \sum_{i=0}^{k} 2^i - \sum_{i=0}^{k} b_i 2^i = 1 + \sum_{i=0}^{k} (1 - b_i) 2^i = \sum_{i=0}^{k-1} c_i 2^i,
where ci=1bic_i = 1 - b_i for 1i<k1 \le i < k and c0=1c_0 = 1. More visually, the effect of one turn is
(1bk1bk2b2b11)2(bk1bk2b2b11)2 (1 b_{k-1} b_{k-2} \cdots b_2 b_1 1)^2 \mapsto (\overline{b_{k-1} b_{k-2} \cdots b_2 b_1} 1)^2
where 0=1\overline{0} = 1 and 1=0\overline{1} = 0. This new number has at most kk binary digits, but it may have fewer if bk1b_{k-1} was equal to 11.
In general, all the leading digits 11 will be lost, i.e. if bk=bk1==bkj+1=1b_k = b_{k-1} = \dots = b_{k-j+1} = 1 and bkj=0b_{k-j} = 0 then the new number will have jj digits less than nn. Therefore, the number of turns to reach 11 is equal to the number of blocks of consecutive equal digits in the binary representation of the initial number, where we ignore the last (units) digit in the count.
For example, the smallest number which allows for ten turns is
1365=(10101010101)2 1365 = (10101010101)^2
---
The smallest number that allows for nine turns is 683=(1010101011)2683 = (1010101011)^2.
The number 1195=(10010101011)21195 = (10010101011)^2 allows for nine turns as well.
Abigail can choose 683683 which enables her to carry out nine steps. If Zoe chooses 11951195 she will also be able to carry out nine steps and so she will win.

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.