Maths Olympiad Prep

Library / /277 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Fifteen stones are placed on a 4×44 \times 4 board, one in each cell, the remaining cell being empty. Whenever two stones are on neighboring cells (having a common side), one may jump over the other to the opposite neighboring 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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

There are three types of cells on the board: corner cells, edge cells, and centre cells. Colour the cells in three distinct colours as follows.

ABCABCABCABCABCA \begin{array}{|c|c|c|c|} \hline \mathrm{A} & \mathrm{B} & \mathrm{C} & \mathrm{A} \\ \hline \mathrm{B} & \mathrm{C} & \mathrm{A} & \mathrm{B} \\ \hline \mathrm{C} & \mathrm{A} & \mathrm{B} & \mathrm{C} \\ \hline \mathrm{A} & \mathrm{B} & \mathrm{C} & \mathrm{A} \\ \hline \end{array}

Suppose there are initially a,b,ca, b, c stones on cells of colours A, B, C, respectively. With each move, one of these numbers will increase by 1, while the other two will decrease by 1. Because there are fourteen moves altogether, the game must end with a,b,ca, b, c of the same parity as they originally had. There are 6,5,56, 5, 5 cells of each colour on the board, so if the game should end with a single stone remaining, the game must begin with

a=6,b=5,c=4 or a=6,b=4,c=5 a=6, b=5, c=4 \quad \text { or } \quad a=6, b=4, c=5 \text {. }

The empty slot should thus have colour B or C. This excludes the corner cells and two of the centre cells. However, by symmetry (changing the colouring), the two remaining centre cells will also be excluded. Hence the empty space at the beginning must be at an edge cell. That the game is indeed winnable in this case can be seen from the sequence of moves here:

!

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.