There is a stone on each square of $n\times n$ chessboard. We gather $n^2$ stones and distribute them to the squares (again each square contains one stone) such that any two adjacent stones are again adjacent. Find all distributions such that at least one stone at the corners remains at its initial square. (Two squares are adjacent if they share a common edge.)
Problem
Source: Turkey TST 1989 - P4
Tags: combinatorics proposed, combinatorics
eyzhang
12.09.2013 03:26
Wouldn't we have to know what n is?
chaotic_iak
12.09.2013 10:40
I can't figure out how to write the solution Basically prove that the second arrangement must be a rotation/reflection of the first, and then just go case-by-case. For $n=1$, the answer is $1$. For odd $n > 1$, the answer is $8$. For even $n$, the answer is $3$. I'm figuring out how to write the solution properly.
manuel153
12.09.2013 11:40
As each of the $(n-2)^2$ inner tokens has four neighbors in the inititial configuration, it also must have four neighbors in the new configuration. This implies that inner stones go to inner cells, and boundary stones go to the boundary. Now consider the corner stone that remains at its initial square: it has two neighboring stones in the inititial configuration that must go to the two neighboring cells in the new configuration. There are two ways for assigning these two neighbors. One can show that once the corner stone plus the position of the neighbors has been fixed, this also fixes the position of all remaining stones (first work along the boundary; then work along the boundary of the inner cells; etc.).