Baltic Way 1991 · Problem 15
Combinatorics
In each of the squares of a chess board an arbitrary integer is written. A king starts to move on the board. As the king moves, 1 is added to the number in each square it "visits". Is it always possible to make the numbers on the chess board:
(a) all even;
(b) all divisible by 3 ;
(c) all equal?
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Games and strategies · Colorings and configurations
Solutions
Solution
Figure 1
Figure 1 demonstrates a possible king's path passing through each square exactly once and finally returning to the initial square. Thus, it suffices to prove part (c) as we can always increase the numbers in all the squares by 1 or 2 if necessary. Moreover, note that for any given square it is possible to modify the path shown in Figure 1 in such a way that this particular square will be passed twice while any other square will still be passed exactly once. Repeating this procedure a suitable number of times for each square we can make all the numbers on the chess board equal.