Maths Olympiad Prep

Library / /20 of 20

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Art and Ben play a game while sharing an m×nm \times n chocolate bar. They take turns breaking the bar into two rectangular pieces along one of the lines and eating the smaller piece. (If the two pieces are equal, they can choose which piece to eat.) Whoever is left with the last 1×11 \times 1 square of chocolate loses. If Art moves first, describe all pairs (m,n)(m, n) for which Ben has a winning strategy.

Solution

Solution:

The answer is all pairs (m,n)(m, n) such that the ratio
R=m+1n+1 R=\frac{m+1}{n+1}
is an integer power of two, that is, the pairs (a1,2ka1)\left(a-1,2^{k} a-1\right) and (2ka1,a1)\left(2^{k} a-1, a-1\right) for a2a \geq 2 and k0k \geq 0. We will show that

a. If RR is a power of two, then it will not remain so after one move;

b. If RR is not a power of two, then some move will make it one.

To prove (a), simply note that at each move, one of the dimensions is decreased at most by half, so either m+1m+1 or n+1n+1 is diminished by a factor strictly between 1 and 2. Thus the new value of RR is sandwiched between two powers of two: R/2R / 2 and RR in the first case, RR and 2R2 R in the second.

As for (b), assume mnm \geq n (the other case is symmetric) so 2k<R<2k+12^{k}<R<2^{k+1} for some k0k \geq 0. We have
2k(n+1)<m+1<2k+1(n+1). 2^{k}(n+1)<m+1<2^{k+1}(n+1) \text{.}
These inequalities imply that one can move to a bar that is [2k(n+1)1]×(n+1)\left[2^{k}(n+1)-1\right] \times(n+1), with RR-value 2k2^{k}.

If RR is initially a power of two, Ben wins by making it that way at each move; otherwise Art wins by the same strategy (in either case ending at the 1×11 \times 1 square, where R=1R=1 ).

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.