12. In the cells of an $n \times n$ chessboard there are altogether 2009 coins. The numbers of coins in any two neighbouring cells (cells sharing a common edge) differ by 1 (some cells may contain no coin). Find the largest possible value of $n$.
(2 marks)
現有一個 $n \times n$ 的棋盤，棋盤的格子裡共有 2009 枚硬幣。在任意兩個相鄰
(即有公共邊) 的格子中, 硬幣的數目均相差 1（有些格子可能沒有硬幣）。求 $n$ 的最大可能値。
12. 63
12. Colour the cells by black and white alternately. It is clear that the numbers of coins in cells of same colour are of the same parity and the numbers of coins in cells of different colours are of different parity. Hence $n$ must be odd, for otherwise the total number of coins must be even since there are an even number of white cells and an even number of black cells.
Now we may assume there are $\frac{n^{2}+1}{2}$ black cells and $\frac{n^{2}-1}{2}$ white cells. Then we must have $\frac{n^{2}+1}{2} \leq 2009$ and $\frac{n^{2}-1}{2} \leq 2009$. Hence $n \leq 63$. It is possible for $n=63$, by putting one coin in each of the $\frac{63^{2}+1}{2}=1985$ black cells, we then put two coins on each of the first 12 white cells of the first row. Together we have $1985+12 \times 2=2009$ coins on the chessboard. It follows that the answer is 63 .