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$.

Pawns on infinite chessboard

Let $k$ be a fixed integer. The cells in a $1 \times \infty$ chessboard is colored in the following fashion: ..., red, blue, green, red, blue, green, ... (and so on) There are a number of pawns on the board. At each turn, we are allowed to choose two pawns $A,B$ and make $A$ "jump over" $B$ so that the new distance is $k$ times the old distance. Formally, we may choose $A$ and $B$ with distance $d$ and move $A$ so that the new distance is $kd$ and $A$ is on a different side of $B$. Multiple pawns may occupy a single cell. Determine all values of $k$ such that, regardless of initial configurations, it's always possible to move the pawns to all occupy the same color.

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.

KBB3 Problem 4

Given a 3x3 chessboard where each cell is colored black or white. At any step, we are allowed to pick any column or any row and flip all the cell colors in that column or row. Prove or disprove: no matter what the initial coloring is, we can always get an all-white board?