Fifteen stones are placed on a $4 \times 4$ board, one in each cell, the remaining cell being empty. Whenever two stones are on neighbouring cells (having a common side), one may jump over the other to the opposite neighbouring cell, provided this cell is empty. The stone jumped over is removed from the board. For which initial positions of the empty cell is it possible to end up with exactly one stone on the board?
Problem
Source: Baltic Way 2017, Problem 6
Tags: combinatorics, combinatorics proposed
28.11.2017 00:03
Oh my god it's almost exactly my problem (that I found quite original), I'm disappointed...
28.11.2017 06:29
Label $16$ cells in the board by usual coordinate $(x,y)$ where $x,y\in \{ 1,2,3,4\}$. We denote number $\omega^{i+j}$ to the cell $(i,j)$ where $\omega =e^{\frac{i\pi }{3}}$. Initially, the sum of number on the board is equal to $k_1\omega +k_2\omega^2 +k_3$ where $(k_1,k_2,k_3)\in \{ (5,5,5),(4,6,5),(5,6,4)\}$. Note that, in each move, the sum of numbers on the board changes from $a_1\omega +a_2\omega^2 +a_3$ to $a_1'\omega +a_2'\omega_2+a_3'$ where $(a_1',a_2',a_3')\in \{ (a_1+1,a_2-1,a_3-1),(a_1-1,a_2+1,a_3-1),(a_1-1,a_2-1,a_3+1)\}$. This mean the parity of $|a_1-a_2|,|a_2-a_3|$ always be the same. If $(k_1,k_2,k_3)$, we get that the sum of number of the board can't be $\omega$ or $\omega^2$ or $1$ (since $|5-5|=0$). So, the blank cell can't have coordinate $(i,j)$ where $i+j\equiv 2\pmod{3}$. This leaves all $8$ border non-corner cells and other $2$ cells at the center. By symmetry, we can also eliminates two cells at the center, so we've $8$ border non-corner possible blank cells. The rest is to show that this is possible, which is fun and not hard.
28.11.2017 06:48
I would recommend using variables other than $i,j$ to indicate indices where you also use $i=\sqrt{-1}$ later.
28.11.2017 13:25
Dark lord, what's your motivation to consider such invariant ? It looks really weird to me.
28.11.2017 15:59
As usual, let's colour the board. As you can notice, each move moves the quantity of stones on 3 cases on the same line (column or row). Then, we're lead to colour in 3 colours our board. Say we colour in Red, Blue, White, in this order, where the top left corner is red. We label cells with usual coordinates (x,y) with x and y two integers beetween 1 and 4. Let r, b and w the number of stones on respectively red, blue and withe cases. Note that at each move, the parity of each quantity change. As we want to end up with only one stone, two quantities must be at the same parity and the last one at a different parity in the initial state. Moreover, with our way of colourig, we have exactly in total 6 red cases, 5 blue cases and 5 white cases. If we initially remove a stone from a red case, all the numbers r, b and w we'll be at the same parity (r=b=w=5). So we have to remove the initial stone from a blue case or a white case. By symmetry, we note that we just have to study the cases (1,4), (2,4) and (2,3). But (1,4) and (2,3) are red, so we can't remove the stone one these cases. It remains the (2,4). Playing around a bit, you see you can finish the game with only this stone removed. So same answer as Dark Lord : the initial stone was removed from a case on an edge but not on a corner.