Partition Game

Alice and Bob are playing a game as follows. Originally there are $n > 1$ piles containing $s$ stones each. Alice starts by taking the first turn and at each step, the player chooses one pile and discards the other piles. Then that player divides the stones from that one pile into $n$ piles, such that each pile still contains at least 1 stone. The player that cannot move loses.

Determine all $s$ such that Alice has a winning strategy

Solution

We classify every natural numbers into winning numbers or losing numbers with the following recursion: The numbers $1, \dots, n-1$ are losing numbers. If a number can be partitioned into losing numbers, then it's a winning number. Otherwise it's a losing number. In other words, any given partition of a losing number must contain a winning number.

Now the game is a standard Sprague-Grundy game. If a player receives a state where one pile contains a winning number, then that state is a winning state. For example, $n$ is a winning number because the player can split it into ones, regardless of what the other numbers in the pile are. If a player receives a state where all piles are losing numbers, then it's a losing state.

Let $m=n-1$. Now we establish the base cases. $1, \dots, m$ are losing numbers. Then $n$ can be partitioned into all ones, and $mn$ can be partitioned into all $m$'s. It's easy to show that all the numbers in between can also be partitioned into summands between $1$ and $m$ inclusive, so $n,\dots,mn$ are winning numbers.

Now we claim: Let $x \equiv p \mod mn$ then $x$ is a winning number if and only if $p = 0$ or $p \geq n$, and it is a losing number if and only if $p \in [1,m]$. We prove it by induction on $k = \lceil x / mn \rceil$. The case of $k = 1$ is proven by the base case above.

Now suppose we have a number $x$ with residue in $[1,m] \mod mn$ and there is a way to partition this number into $n$ summands, all while staying within $[1,m] \mod mn$. The smallest sum (in the residue space) that can be attained is $n$, and the largest sum is $mn$, and they are all outside of $[1,m]$, a contradiction. So some of the summands must have residue $0$ or $\geq n \mod mn$. Let $y$ be this summand. Note that $ \lceil y / mn \rceil < \lceil x / mn \rceil$ in each of these cases. So $x$ is a losing number by induction hypothesis.

Now suppose we have a number $y$ divisible by $mn$, then we can partition it into $n$ numbers all having residue $m$. The easiest is of course to have the first $m$ terms $m$ and have the last term $y - m^2 = kmn - m^2 = (k-1)mn + m$. Each of these numbers are losing numbers with less quotient than $y$, so $y$ is a winning number.

Next, suppose we have $y$ with residue $[n, mn-1]$. Using the same argument as above, we can see that it can always be decomposed into the sum of $n$ numbers with residue $[1,m]$. However, the quotient of the summands are not necessarily less than $y$, but we have proved that the set in $[1,m]$ with quotient $k$ are losing numbers as well.

Moving coins across the board

On a $1 \times 2018$ chess-board, the $n (n < 2018)$ left-most squares contain 1 coin each. Alice and Bob are playing a game, where on each turn the player may choose a coin and move it to the right one or two units. The only condition is that each square may only contain one coin at a time (no "stacking"), except the last square (right-most square). Alice goes first. The player who cannot make a legal move loses. Determine all $n$ such that Alice has a winning strategy.

Solution

Label each square by its distance from the right-most square. So the right-most square is called square zero, and the left-most square is called square 2017. Suppose $(a_1, a_2, \dots, a_k)$ denotes the condition that there is a coin on each of the cells $a_1, \dots, a_k$ and the rest of the coins are in the square zero. WLOG, we may assume $a_1 < a_2 < \dots < a_k$.

Claim:

We claim that $(a_1, \dots, a_k)$ is a losing position if and only if $a_1 + \dots + a_k$ is divisible by 3.

First note that the game ends only when there's no more legal move left, and that's when all the coins are on square zero. So as long as the sum of the coin numbers are greater than zero, there is always a legal move available. At the very least, the coin with the lowest number can be moved to the right 1 or 2 steps (possibly reaching zero in the process).

Lemma:

If the sum of the numbers are not divisible by 3, there is always a legal move to make it divisible by 3 within one turn.

Note that our claim is a corollary of the lemma. If the sum of the numbers is divisible by 3, then no matter what move you do, you can only reduce it by 1 or 2. Based on the lemma, the opponent can always counter it by bringing down to the next multiple of 3. Therefore, your opponent will never face the situation without any legal move. Conversely, if it's not divisible by 3, you can always bring it to a multiple of 3 within one turn so that your opponent is facing a losing position next. And your winning strategy is always to keep the sum of the numbers divisible by 3.

Proof of lemma:

If the the sum of the numbers is $3m+1$, then you only need to move the lowest-numbered coin down by 1. This is always possible because it is at least 1. If the sum of the numbers is $3m+2$, then you need to move ANY coin down by 2. Suppose that this is not possible, either due to prospect of collision or running against the end of the board. That means the following:

1. There are no two consecutive empty cells. If there are two or more consecutive empty cells, then the coin to the left of that block can be moved down by two. This means that $a_i - a_{i-1} = 1,2$ for each $i$.

2. There is nothing on cell 2, because otherwise we can always move it to cell 0 directly.

3. There is no "jumping over" possible. Meaning, if cell $x$ is empty but $x+1,x+2$ are both occupied, we can take $x+2$ and move it to $x$. So this configuration is not allowed: EMPTY, OCCUPIED, OCCUPIED.

This means cell 1 has a coin on it. $a_1 = 1$. Since 2 is empty, then 3 must have a coin on it ($a_2 = 3$). If 4 has a coin on it, then it violates condition 3 above, so 4 must be empty. That means 5 must be occupied (by condition 1). We can continue this pattern indefinitely, to arrive at the conclusion that current condition must be: $(1,3,5, \dots, 2k-1)$. The sum of the numbers is therefore $1 + 3 + \dots + 2k-1 = k^2$, which cannot be $3m+2$. Contradiction. Hence it's always possible to choose a coin to move down by 2. This completes our proof of the lemma.

Now, the initial condition is $(2018-(n-1), 2018-(n-2), \dots, 2018)$, so that the sum of the numbers is: $n(4037-n)/2$. For this to be divisible by 3, either $n$ is divisible by 3, or $n \equiv 2 \mod 3$. These are the losing positions. So in order for Alice to have winning strategy, $n \equiv 1 \mod 3$.

Marbles in 3 buckets

Given 3 buckets, each containing $n$ marbles. Alice and Bob are playing a game, where on each turn, the player may remove 1, 2, or 3 marbles from a single bucket. Alice goes first. The player who removes the last marble wins. Determine all $n$ such that Alice has a winning strategy.

Solution

If $n$ is divisible by 4 then Bob has a winning strategy, and if $n$ is not divisible by 4 then Alice has a winning strategy.

First note that $(4m,k,k)$ is a losing position for any $k \geq 0,m > 0$. Because if you remove $p$ marbles from the first bucket, your opponent may remove $4-p$ marbles to go back to $(4(m-1), k k)$. And if you remove from any of the second or third pile, your opponent may mirror that to go back to $(4m, k-p, k-p)$. Thus, no matter what you do, your opponent always has a legal move to make.

Therefore if $n$ is divisible by 4, assuming Bob plays optimally, Alice loses the game.

But if $n$ is not divisible by 4, say $n = 4m+a, a=1,2,3$. Then Alice may remove $a$ from the first bucket, to arrive at $(4m,n,n)$ which is a losing position for Bob.

Generalization

If there are $n$ buckets of $n$ marbles, we can employ the same strategy. The goal is to force your opponent into a "symmetric" situation where no matter what he/she does, you can always mirror it.

If $n$ is divisible by 4, then $(n,n,\dots,n)$ is a losing position because no matter what you do, your opponent can always mirror it. In general, the situation where there are an even number of buckets left and each pair of buckets contains the same number of marbles is a losing position.

If $n=4m+1,4m+3$, then you can employ the same strategy as above. Alice transforms the configuration into $(4m, a,a, b,b, \dots, z,z)$ and from there no matter what Bob does, Alice can always mirror it.

Variation

Now, suppose there's only $n$ marbles total and it is to be distributed among all 3 buckets, with each bucket containing at least one marble. Alice determines the distribution, and Bob makes the first "regular" turn. Determine all numbers $n$ such that there exists a way for Alice to distribute in such a way that Bob always loses.

Solution

At this point, we have to characterize the conditions in which configuration $(a,b,c)$ is a losing position. It's clear to see that $(a,0,0)$ is a losing position if and only if $a \equiv 0 \mod 4$.

Now consider the configuration $(a,b,0)$. If $a \equiv b \mod 4$ then this is a losing position, because the opponent can always mirror you move to keep the condition true. Therefore, if $a \neq b \mod 4$, it is a winning position because we can turn it into the above-mentioned losing position for our opponent.

Now consider the configuration where there are three non-zero buckets left. As we saw above, $(4a,b,b)$ is a losing position because your opponent can always mirror your steps, and restoring to original configuration, and consequently, $(a,b,b)$ is a winning position if $a \neq 0 \mod 4$ because you can turn it into the form $(4a,b,b)$.

We can take this reasoning one step further by claiming, the configuration $(a,b,c)$ where $b \equiv c \mod 4$ is a losing position if and only if $a \equiv 0 mod 4$. Indeed, if $a$ is divisible by 4, then any move you make in the first bucket will be countered in the first bucket, and any move you make in the second or third buckets will also be countered to keep $b \equiv c \mod 4$. Thus either you will bring $a$ below 4 and your opponent can empty the first bucket, leaving you to $(0,b,c)$ which is a losing position, or you will empty one of the second or third buckets first. In the latter case, then your opponent can still mirror it to arrive at $(a,0,c)$ where both $a,c$ are divisible by 4, which is a losing position. Conversely, if $a$ is not divisible by 4, you can make it divisible by 4 to be a losing position for your opponent.

Finally we prove that $(a,b,c) \equiv (1,2,3) \mod 4$ is a losing position, because any move that is made from here will result in a winning position. If we take from first bucket, we now get $(2/3/0, 2,3) \mod 4$ all of which are winning positions. If you take from second bucket, we get $(1, 3/0/1, 3)$ also winning positions, similarly if we do from third bucket. The point is that there is no way to avoid $(a,a,b)$ form where $b $ is not divisible by 4, or $(0,a,b)$ form.

Thus, if $n > 4$ is even, Alice has a winning strategy as follows. If $n = 4m$ then Alice distributes the marbles as $(4(m-1),2,2)$. If $n=4m+2$ she distributes it as $(4m,1,1)$. Both are losing positions Bob. But if $n=4$, then Bob has a winning strategy. Alice has no choice but to distribute the marbles as $(1,1,2)$ initially, and Bob can turn it into $(1,1,0)$ which is a losing position for Alice.

If $n$ is odd, Bob has a winning strategy no matter how Alice distributes the marbles. If all the three buckets contain odd number of marbles, then two of them will be congruent modulo 4, and the third one will not be divisible by 4, and that is a winning position for Bob. If two buckets contain even numbers and the third one odd, we have two choices. Either the two even buckets are both $\equiv 2 mod 4$, which means it's still a winning position for Bob, or at least one of them is divisible by 4, which is also a winning position for Bob.

Bottom line, Alice has a way to distribute the marbles into a losing position for Bob if and only if $n$ is even and $n > 4$.

Marking number game

Let $n > 2$ be an even number. On the board, there are numbers $1, 2, \dots, n$, and initially the number 1 is marked, and no other numbers are marked. Alice and Bob are playing a game, with Alice moving first. On each turn, they may choose a number $k$ that is currently unmarked, and mark it, provided: $k+1$ was previously marked, OR $k$ is even and $k/2$ was previously marked. The player who gets to mark the number $n$ wins the game.

Determine all $n$ such that Alice has a winning strategy.

Solution

As soon as one player marks $n/2$, then he/she loses, because the opponent can mark $n$ directly after that. Also, the number $n$ can be marked ONLY after $n/2$ is marked (by virtue of $n/2$ being marked, since there is no number $n+1$ on the board). Therefore, the crux of the game is to avoid the number $n/2$ at all costs.

Suppose $n = 2m$. Define the numbers in set $\{ 2,3,\dots, n-1 \}$ to be "accessible" if it can be marked without ever marking $m$. Obviously $m$ is not accessible. Let $A$ be the set of accessible numbers. For example, for $n=12$ the accessible numbers are: $A = \{ 2, 3, 4, 7, 8 \}$. Note that 6 is not accessible by definition. 5 is not accessible because in order to mark 5, we'd have to go through 6. 11 is not accessible because it can't be reached without marking 12, which has to go through 6. 10 is also not accessible because it can only be reached through 11 or 5, both of which are not accessible. Therefore 9 is also not accessible.

Now, as long as there's an unmarked number in $A$, then the current player can always choose a legal move to play. Not all unmarked numbers in $A$ will be eligible to be marked, but by the construction of $A$, we can reach that number through other numbers that have been marked (and therefore also in $A$), so as long as there exists an unmarked number in $A$, there is a legal move to be played.

As soon as all numbers in $A$ are marked, then the next person has to mark $m$, and the other player can win immediately. In the case of $n=12$ above, 10 will not ever be marked because as soon as 6 is marked, the next person marks 12. Therefore the winner of the game (assuming both sides play optimally) depends on the parity of $|A|$. Alice has a winning strategy if and only if $|A|$ is odd.

Generally all the numbers from $\{2, 3, \dots, 2m-2 \}$ are accessible, with a handful of exception. $m$ is by definition inaccessible, and $2m-1$ is also inaccessible. So we want to list all the numbers that are not accessible. We divide into two cases.

If $m$ is odd:

Consider the sequence: $1,2,4,3,6,5,8,7, \dots, 2k, 2k-1, 2k+2, 2k+1, \dots, 2m-2, 2m-3$. That is a legal sequence to mark numbers. Therefore, almost all numbers in the set $\{2, 3, \dots, 2m-2 \}$ are accessible except $m$, because we can simply go through the sequence, and only skipping $m$. No further interruption to the sequence will occur because the highest number in the sequence is $2m-2 < 2m$ so it's not affected by the fact that $m$ was never marked. Thus, $A = \{2, \dots, 2m-2 \} - \{ m \}$, and $|A| = 2m-4$. This means Alice does not have a winning strategy because Bob has a winning strategy.

If $m$ is even:

Same as before, we go through the sequence, but skipping $m$. This has several ramifications. First, because $m$ is even, then $m-1$ is not accessible. Thus, there are two numbers that are also "deleted" from that sequence later on: $2m-2, 2m-3$. The rest of the sequence is not affected, because $m+2, m+4,m+6,\dots, 2m-4$ can still be marked. Thus: $|A| = 2m-3 - 4 = 2m-7$. This means Alice has a winning strategy.

This reasoning breaks down when $m=2$ because then $2m-2 = 2$ so there was no other choice and Bob wins. But this is the only corner case. Therefore, Alice has a winning strategy if and only if $n > 4$ and $n$ is divisible by 4.

Lights forming a hexagon

Six lights are placed such that they form a regular hexagon. At each turn, we're allowed to do one of the following:

1. Toggle three consecutive lights

2. Toggle three lights that form an equilateral triangle

3. Toggle two diametrically opposite lights

Prove or disprove, for any given starting configuration, we can turn off all the lights through a series of turns as described above.

Solution

Answer: we cannot.

Label the lights as 1,2,3,4,5,6, and denote each move as follows:

$A_i$: toggling lights $i, i+1, i+2$. There are 6 such moves: $A_1, \dots, A_6$.

$B_i$: toggling an equilateral with $i$ as one of its vertices. Obviously we only need to consider $B_1, B_2$.

$C_i$: toggling $i$ and its opposite. Again, we only need to consider $C_1, C_2, C_3$.

$D$: toggling all the lights. Although this is not one of the moves allowed explicitly in the problem statement, it can be achieved by the combination of $A_1+A_4$ (as well as many others), so it is effectively a legal move.

From a set of moves, we're allowed to remove it if it can be achieved by a combination of all the other moves remaining in the set. So from the set of all the moves described above, we can remove $A_4, A_5, A_6$ because they can be achieved by $D + A_1, D+A_2, D+A_3$ respectively.

Likewise, we can remove $B_2 = B_1 + D$ and $C_3 = C_1+C_2+D$. So now we're down to $\{A_1,A_2,A_3,B_1,C_1,C_2,D\}$. Now notice that: $A_2 = C_1 + A_1$, $A_3 = C_1 + C_2 + A_1$ so we remove them as well, leaving us with $\{A_1,B_1,C_1,C_2,D\}$.

Now although the number of possible move sequences is infinite, the number of reachable configurations from an all-off configuration is limited. There are five moves left in our set. We have not yet proved that they're all truly independent (i.e. we can no longer remove any more), but we don't need to. For each move in that set, it only matters whether that move is performed an even or odd number of time. In algebraic lingo, these moves are commutative and self-inverse. So that means there are at most $2^5$ configurations reachable from an all-off configuration, but we have $2^6$ total configurations. Each sequence of moves are its own inverse, so that means there are 32 configurations such that we cant turn off all the lights.

If we're asked to identify such configuration, we note the following: the configuration where only 1 light is on is not reachable from an all-off configuration. If this were possible, then we could apply that same sequence of moves (rotated appropriately) to achieve any desired configuration.

Replacing number on the board

In a blackboard, the number 2012 is initially written. On each turn, the student can choose on of the three numbers: 6, 1006, 1509, and multiply it with the existing number on the board. The existing number is then erased and replaced with the new product.

The teacher has a specific integer $k > 1$ in mind, and the goal for the student is to get the number of the board to have form $n^k$ where $n$ is an integer.

Determine all values of $k$ such that, after a finite number of turns, the number of the board will have the desired form.

Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.