Question 60
A $3n\times3n$ board has rows and columns numbered $1,\dots,3n$. Color cell $(x,y)$ A, B or C according as $x+y$ is $0$, $1$ or $2$ modulo three. Place one token, colored A, B or C, in every cell, with $3n^2$ tokens of each color.
Suppose the tokens can be permuted so that every token moves a distance at most $d$, every A-token replaces a B-token, every B-token replaces a C-token, and every C-token replaces an A-token. Prove that another permutation exists in which every token moves at most $d+2$ and ends in a cell of its own color.
Suppose the tokens can be permuted so that every token moves a distance at most $d$, every A-token replaces a B-token, every B-token replaces a C-token, and every C-token replaces an A-token. Prove that another permutation exists in which every token moves at most $d+2$ and ends in a cell of its own color.