A box $3\times5\times7$ is divided into unit cube cells. In each of the cells, there is a cockchafer. At a signal, every cockchafer moves through a face of its cell to a neighboring cell. (a) What is the minimum number of empty cells after the signal? (b) The same question, assuming that the cockchafers move to diagonally adjacent cells (sharing exactly one vertex).
Problem
Source: 2001 Moldova MO Grade 10 P8
Tags: game, combinatorics
building
20.05.2021 02:56
The answer is $1$. Color the cells black and white in a 3D checkerboard pattern, with black in the corners. Then there are $53$ black cells and $52$ white ones. At the signal, every cockchafer moves to a cell with the opposite color, so we will end up with $52$ cockchafers in black cells and $53$ in white ones. Thus, at least one black cell must be empty. To show that this minimum is attained, have the cockchafers in rows 1-2 swap rows, have the remaining cockchafers in columns 1-4 swap columns (1<->2 and 3<->4), and have the remaining cockchafers at height 1-6 swap heights (1<->2, 3<->4, 5<->6). The lone remaining cockchafer at (3, 5, 7) can go wherever.
The answer is $35$. Note that there are $70$ cells in odd-numbered rows and $35$ in row 2. At the signal, every cockchafer moves to a row with opposite parity, so we will end up with $70$ cockchafers in row 2 and $35$ in the odd rows. Hence, at least $35$ cells will be empty. To show that this minimum is attained, move the cockchafers in row 2 according to the following diagram, where blue = move to the corresponding cell in row 1, red = move to the corresponding cell in row 3:
[asy][asy]
unitsize(1cm);
add(grid(7,5,gray));
int[] codes={0, 0, 0, 0, 0, 0, 6, 5, 3, 3, 3, 3, 3, 3, 5, 5, 5, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 6, 5, 3, 3, 3, 3, 3, 3};
for (int i=0; i<7; ++i) {
for (int j=0; j<5; ++j) {
int code = codes[7*j+i];
pen col = red;
if (code < 4) {
col = blue;
}
real dx = -1;
if (code%4 < 2) {
dx = 1;
}
real dy = -1;
if (code%2 == 0) {
dy = 1;
}
draw((i+0.5+0.05*dx, j+0.5+0.05*dy)--(i+0.5+0.95*dx, j+0.5+0.95*dy), col, EndArrow);
}
}
[/asy][/asy]
This sends every cockchafer in row 2 to a different cell, so at least $35$ cells in the odd rows will be non-empty. Also, for every cell to which a row 2 cockchafer was sent, have the cockchafer in that cell swap with the row 2 cockchafer, so that all $35$ cells in row 2 are non-empty. The remaining cockchafers can go wherever. This gives at least $70$ non-empty cells, hence at most $35$ empty cells, as desired.