Maths Olympiad Prep

Library / /61 of 61

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Canada

Problem:

Nina and Tadashi play the following game. Initially, a triple (a,b,c)(a, b, c) of nonnegative integers with a+b+c=2021a+b+c=2021 is written on a blackboard. Nina and Tadashi then take moves in turn, with Nina first. A player making a move chooses a positive integer kk and one of the three entries on the board; then the player increases the chosen entry by kk and decreases the other two entries by kk. A player loses if, on their turn, some entry on the board becomes negative.

Find the number of initial triples (a,b,c)(a, b, c) for which Tadashi has a winning strategy.

Solution

Solution:

The answer is 3number of 1’s in binary expansion of 2021=38=65613^{\text{number of 1's in binary expansion of } 2021}=3^{8}=6561.

Throughout this solution, we say two nonnegative integers overlap in the 22^{\ell} position if their binary representations both have a 1 in that position. We say that two nonnegative integers overlap if they overlap in some position. Our central claim is the following.

Claim 1. A triple (x,y,z)(x, y, z) is losing if and only if no two of x,y,zx, y, z overlap.

Let d(a)d_{\ell}(a) denote the bit in the 22^{\ell} position of the binary representation of aa. Let &\& denote the bitwise and operation: x&yx \& y is the number satisfying d(x&y)=d(x)d(y)d_{\ell}(x \& y)=d_{\ell}(x) d_{\ell}(y) for all \ell.

Lemma 1. Let x,y,zx, y, z be nonnegative integers, at least one pair of which overlaps. Define x=(x+y)&(x+z)x^{\prime}=(x+y) \&(x+z) and y,zy^{\prime}, z^{\prime} cyclically. At least one of the inequalities x<x,y<y,z<zx<x^{\prime}, y<y^{\prime}, z<z^{\prime} holds.

Proof. Let \ell be maximal such that two of x,y,zx, y, z overlap in the 22^{\ell} position. We case on how many of the additions x+y,x+z,y+zx+y, x+z, y+z involve a carry from the 22^{\ell} position to the 2+12^{\ell+1} position, and on the values of d+1(x),d+1(y),d+1(z)d_{\ell+1}(x), d_{\ell+1}(y), d_{\ell+1}(z). Because at least two of d(x),d(y),d(z)d_{\ell}(x), d_{\ell}(y), d_{\ell}(z) equal 1, at least one of the additions x+y,x+z,y+zx+y, x+z, y+z involves a carry from the 22^{\ell} position.

Case 1. One carry.

WLOG let x+yx+y be the addition with the carry. Then, d(x)=d(y)=1d_{\ell}(x)=d_{\ell}(y)=1 and d(z)=0d_{\ell}(z)=0. Since x,y,zx, y, z do not overlap in any position left of the 22^{\ell} position, the binary representations of z,zz, z^{\prime} agree left of the 22^{\ell} position. As the additions x+zx+z and y+zy+z do not involve a carry from the 22^{\ell} position, we have d(x+z)=d(y+z)=1d_{\ell}(x+z)=d_{\ell}(y+z)=1, and thus d(z)=1d_{\ell}\left(z^{\prime}\right)=1. Thus z>zz^{\prime}>z, as desired.

Case 2. At least two carries: x+yx+y and x+zx+z carry and d+1(y)=d+1(z)=0d_{\ell+1}(y)=d_{\ell+1}(z)=0, or cyclic equivalent. (y+zy+z may or may not carry.)

Let ii be maximal such that d+1(x)==d+i(x)=1d_{\ell+1}(x)=\cdots=d_{\ell+i}(x)=1 (possibly i=0i=0). By maximality of ,d+1(y)=d+1(z)==d+i(y)=d+i(z)=0\ell, d_{\ell+1}(y)=d_{\ell+1}(z)=\cdots=d_{\ell+i}(y)=d_{\ell+i}(z)=0. By maximality of i,d+i+1(x)=0i, d_{\ell+i+1}(x)=0.

If d+i+1(y)=d+i+1(z)=0d_{\ell+i+1}(y)=d_{\ell+i+1}(z)=0, then d+i+1(x+y)=d+i+1(x+z)=1d_{\ell+i+1}(x+y)=d_{\ell+i+1}(x+z)=1, so d+i+1(x)=1d_{\ell+i+1}\left(x^{\prime}\right)=1. The binary representations of xx and xx^{\prime} agree to the left of the 2+i+12^{\ell+i+1} position, so x>xx^{\prime}>x.

Otherwise, WLOG d+i+1(y)=1d_{\ell+i+1}(y)=1 and d+i+1(z)=0d_{\ell+i+1}(z)=0. (Note that, here we in fact have i1i \geq 1.) Then d+i+1(y+z)=d+i+1(x+z)=1d_{\ell+i+1}(y+z)=d_{\ell+i+1}(x+z)=1, so d+i+1(z)=1d_{\ell+i+1}\left(z^{\prime}\right)=1. The binary representations of zz and zz^{\prime} agree to the left of the 2+i+12^{\ell+i+1} position, so z>zz^{\prime}>z.

Case 3. At least two carries, and the condition in Case 2 does not occur.

WLOG let x+y,x+zx+y, x+z involve carries. Since the condition in Case 2 does not occur, d+1(y)=1d_{\ell+1}(y)=1 or d+1(z)=1d_{\ell+1}(z)=1. In either case, d+1(x)=0d_{\ell+1}(x)=0. WLOG d+1(y)=1d_{\ell+1}(y)=1 and d+1(z)=0d_{\ell+1}(z)=0.

Since the condition in Case 2 does not occur, y+zy+z does not involve a carry from the 22^{\ell} position. (Otherwise, x+yx+y and y+zy+z carry and d+1(x)=d+1(z)=0d_{\ell+1}(x)=d_{\ell+1}(z)=0.) Then d+1(x+z)=d+1(y+z)=1d_{\ell+1}(x+z)=d_{\ell+1}(y+z)=1, so d+1(z)=1d_{\ell+1}\left(z^{\prime}\right)=1. The binary representations of zz and zz^{\prime} agree to the left of the 2+12^{\ell+1} position, so z>zz^{\prime}>z.

Proof of Claim 1. Proceed by strong induction on x+y+zx+y+z. There is no base case.

Suppose by induction the claim holds for all (x,y,z)(x, y, z) with sum less than NN. Consider a triple (x,y,z)(x, y, z) with x+y+z=Nx+y+z=N.

Suppose no two of x,y,zx, y, z overlap. If all moves from this position lead to positions with a negative coordinate, (x,y,z)(x, y, z) is a losing position, as claimed. Otherwise, the player increases or decreases all coordinates by kk. Consider the smallest mm such that dm(k)=1d_{m}(k)=1. The player's move will toggle each of dm(x),dm(y),dm(z)d_{m}(x), d_{m}(y), d_{m}(z). Since at most one of the original dm(x),dm(y),dm(z)d_{m}(x), d_{m}(y), d_{m}(z) is 1, at least two of the new dm(x),dm(y),dm(z)d_{m}(x), d_{m}(y), d_{m}(z) will be 1. So, two of the new x,y,zx, y, z overlap. By induction, the new (x,y,z)(x, y, z) is winning. Thus the original (x,y,z)(x, y, z) is losing, as claimed.

Conversely, suppose at least one pair of x,y,zx, y, z overlap. By Lemma 1, at least one of x<x,y<y,z<zx<x^{\prime}, y<y^{\prime}, z<z^{\prime} holds. WLOG x<xx<x^{\prime}. Let the player to move choose k=xxk=x^{\prime}-x, decrease y,zy, z by kk, and increase xx by kk. The new coordinates are nonnegative, as
yk=x+yx0 y-k=x+y-x^{\prime} \geq 0
because xx+yx^{\prime} \leq x+y, and similarly for the zz coordinate. Moreover, the binary representation of the new xx consists of the 1's in the binary representations of both x+yx+y and x+zx+z; the binary representation of the new yy consists of the 1's in that of x+yx+y but not x+zx+z; and the binary representation of the new zz consists of the 1's in that of x+zx+z but not x+yx+y. So, no two of the new x,y,zx, y, z overlap. By induction, the new (x,y,z)(x, y, z) is losing. Thus the original (x,y,z)(x, y, z) is winning, as claimed.

We use Claim 1 to count the losing positions (x,y,z)(x, y, z) with
x+y+z=2021=111111001012 x+y+z=2021=11111100101_{2}
In each position where d(2021)=0d_{\ell}(2021)=0, losing positions must have d(x)=d(y)=d(z)=0d_{\ell}(x)=d_{\ell}(y)=d_{\ell}(z)=0. In each position where d(2021)=1d_{\ell}(2021)=1, the bit triplet (di(x),di(y),di(z))\left(d_{i}(x), d_{i}(y), d_{i}(z)\right) is one of (1,0,0),(0,1,0),(0,0,1)(1,0,0),(0,1,0),(0,0,1). This gives a count of 38=65613^{8}=6561.

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.