Nina and Tadashi play the following game. Initially, a triple $(a, b, c)$ of nonnegative integers with $a+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 $k$ and one of the three entries on the board; then the player increases the chosen entry by $k$ and decreases the other two entries by $k$. A player loses if, on their turn, some entry on the board becomes negative.

Find the number of initial triples $(a, b, c)$ for which Tadashi has a winning strategy.
The answer is $3^{\text {number of 1's in binary expansion of } 2021}=3^{8}=6561$.
Throughout this solution, we say two nonnegative integers overlap in the $2^{\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)$ is losing if and only if no two of $x, y, z$ overlap.
Let $d_{\ell}(a)$ denote the bit in the $2^{\ell}$ position of the binary representation of $a$. Let $\&$ denote the bitwise and operation: $x \& y$ is the number satisfying $d_{\ell}(x \& y)=d_{\ell}(x) d_{\ell}(y)$ for all $\ell$.

Lemma 1. Let $x, y, z$ be nonnegative integers, at least one pair of which overlaps. Define $x^{\prime}=(x+y) \&(x+$ $z)$ and $y^{\prime}, z^{\prime}$ cyclically. At least one of the inequalities $x<x^{\prime}, y<y^{\prime}, z<z^{\prime}$ holds.
Proof. Let $\ell$ be the smallest index such that $d_{\ell}(x+y) \neq d_{\ell}(x+z)$. Then $x+y$ and $x+z$ carry from the $2^{\ell}$ position, and $d_{\ell}(y) \neq d_{\ell}(z)$. WLOG $d_{\ell}(y)=1$ and $d_{\ell}(z)=0$. Then $d_{\ell}(x+y)=d_{\ell}(x+z)=1$, so $d_{\ell}\left(x^{\prime}\right)=1$. The binary representations of $x$ and $x^{\prime}$ agree to the left of the $2^{\ell}$ position, so $x^{\prime}>x$, as desired.

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

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

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

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

Case 3. At least two carries, and the condition in Case 2 does not occur.
WLOG let $x+y, x+z$ involve carries. Since the condition in Case 2 does not occur, $d_{\ell+1}(y)=1$ or $d_{\ell+1}(z)=1$. In either case, $d_{\ell+1}(x)=0$. WLOG $d_{\ell+1}(y)=1$ and $d_{\ell+1}(z)=0$.
Since the condition in Case 2 does not occur, $y+z$ does not involve a carry from the $2^{\ell}$ position. (Otherwise, $x+y$ and $y+z$ carry and $d_{\ell+1}(x)=d_{\ell+1}(z)=0$.) Then $d_{\ell+1}(x+z)=d_{\ell+1}(y+z)=1$, so $d_{\ell+1}\left(z^{\prime}\right)=1$. The binary representations of $z$ and $z^{\prime}$ agree to the left of the $2^{\ell+1}$ position, so $z^{\prime}>z$.

Proof of Claim 1. Proceed by strong induction on $x+y+z$. There is no base case.
Suppose by induction the claim holds for all $(x, y, z)$ with sum less than $N$. Consider a triple $(x, y, z)$ with $x+y+z=N$.
Suppose no two of $x, y, z$ overlap. If all moves from this position lead to positions with a negative coordinate, $(x, y, z)$ is a losing position, as claimed. Otherwise, the player increases or decreases all coordinates by $k$. Consider the smallest $m$ such that $d_{m}(k)=1$. The player's move will toggle each of $d_{m}(x), d_{m}(y), d_{m}(z)$. Since at most one of the original $d_{m}(x), d_{m}(y), d_{m}(z)$ is 1 , at least two of the new $d_{m}(x), d_{m}(y), d_{m}(z)$ will be 1 . So, two of the new $x, y, z$ overlap. By induction, the new $(x, y, z)$ is winning. Thus the original $(x, y, z)$ is losing, as claimed.

Conversely, suppose at least one pair of $x, y, z$ overlap. By Lemma 1, at least one of $x<x^{\prime}, y<y^{\prime}, z<z^{\prime}$ holds. WLOG $x<x^{\prime}$. Let the player to move choose $k=x^{\prime}-x$, decrease $y, z$ by $k$, and increase $x$ by $k$. The new coordinates are nonnegative, as

$$
y-k=x+y-x^{\prime} \geq 0
$$

because $x^{\prime} \leq x+y$, and similarly for the $z$ coordinate. Moreover, the binary representation of the new $x$ consists of the 1 's in the binary representations of both $x+y$ and $x+z$; the binary representation of the new $y$ consists of the 1's in that of $x+y$ but not $x+z$; and the binary representation of the new $z$ consists of the 1's in that of $x+z$ but not $x+y$. So, no two of the new $x, y, z$ overlap. By induction, the new $(x, y, z)$ is losing. Thus the original $(x, y, z)$ is winning, as claimed.

We use Claim 1 to count the losing positions $(x, y, z)$ with

$$
x+y+z=2021=11111100101_{2}
$$

In each position where $d_{\ell}(2021)=0$, losing positions must have $d_{\ell}(x)=d_{\ell}(y)=d_{\ell}(z)=0$. In each position where $d_{\ell}(2021)=1$, the bit triplet $\left(d_{i}(x), d_{i}(y), d_{i}(z)\right)$ is one of $(1,0,0),(0,1,0),(0,0,1)$. This gives a count of $3^{8}=6561$.