Suppose there are three empty buckets and $n \ge 3$ marbles. Ani and Budi play a game. For the first turn, Ani distributes all the marbles into the buckets so that each bucket has at least one marble. Then Budi and Ani alternate turns, starting with Budi. On a turn, the current player may choose a bucket and take 1, 2, or 3 marbles from it. The player that takes the last marble wins. Find all $n$ such that Ani has a winning strategy, including what Ani's first move (distributing the marbles) should be for these $n$.
Problem
Source: Indonesian National Science Olympiad 2018, Mathematics P7
Tags: combinatorics
Pathological
26.08.2019 00:28
The answer is all even $n \ge 6.$ For those $n$, Ani can put $4$ marbles in the first bucket and $\frac{n-4}{2}$ in the other two. Afterwards, she can use the following strategy. If Budi takes $x$ marbles from the second (resp. third) bucket, she will take $x$ from the third (resp. second) bucket. Let's now show that for all other $n$, Budi has a winning strategy. In fact, we will characterize all triples of nonnegative integers $(a, b, c)$ such that if there are $a, b, c$ marbles in the first, second, third buckets respectively, at some point in time, then the next player to move will be the one to lose. Call such triples $(a, b, c)$ losing . By convention we will say that $(0, 0, 0)$ is losing. Claim. A triple $(a, b, c) \in \mathbb{Z}_{\ge 0}^3$ is losing if and only if either: 1. Two of $a, b, c$ are congruent modulo $4$, and the other one is $0$ mod $4$ or 2. $a, b, c$ are congruent to $1, 2, 3$ modulo $4$ in some order Proof. Call a triple of nonnegative integers satisfying one of the two conditions above golden. Let's first establish two observations. Firstly, we will show that if $(a, b, c)$ is golden, then the removal of $1, 2,$ or $3$ will always make it not golden. Secondly, we will show that if $(a, b, c)$ isn't golden, we can always remove $1, 2,$ or $3$ marbles from some bucket to make it golden. Both of these facts are obvious, and the proofs of these results are left as exercises to the reader. With these observations, the claim easily follows. $\blacksquare$ From the claim, it is immediate that no triple $(a, b, c) \in \mathbb{Z}_{\ge 0}^3$ so that $a+b+c$ is odd can be losing. Therefore, no matter how Ani distributes the marbles among the buckets for odd $n$, Budi can always win because the configuration will not be losing. To finish, it suffices only to show that Budi wins for $n = 4.$ However, this is obvious, as there must be $2, 1, 1$ marbles in the three buckets in some order, and so Budi can guarantee victory by taking both marbles from the bucket with $2$ as his first move. $\square$