Gnomes Solution
I recently posted a gnome puzzle by Alexander Gribalko.
Puzzle. Nine gnomes repeat the following procedure three times. They arrange themselves on a 3 by 3 chessboard with one gnome per cell and greet all of their orthogonal neighbors with handshakes. Prove that not all pairs of gnomes greet each other.
As often happens with my blog puzzles, I used this puzzle as homework for my students. They calculated that the total number of handshakes needed for all nine gnomes to greet each other is 36. On the other hand, each arrangement of gnomes creates 12 handshakes. This means that the numbers are tight: no greeting can be wasted, and every pair of gnomes need to greet each other exactly once. The students then studied different cases to prove this was impossible.
In each arrangement, a gnome can have either 2, 3, or 4 handshakes. Hence, we can distribute handshakes over three placements as 2+2+4 or 2+3+3. It follows that if a gnome is ever in the center of the grid, he has to be in a corner for the other two arrangements. Therefore, the three gnomes who end up in the center for one of the arrangements never greet each other.
However, I always love solutions that involve coloring the board in a checkerboard manner. Here is my solution.
Share:Solution. Let’s color the board in a checkerboard manner. We assign each gnome a binary string, of length 3, describing the colors of the cells where the gnome was in each placement. There are 8 different possible strings. It follows that at least two gnomes are assigned the same string. But they can’t greet each other if they are standing on the same colors in each arrangement!
Kai:
Any idea about the version of 16 gnomes on a 4×4 board for 5 times? I wrote some scripts but it seems quite challenging to solve the problem by random trial-and-error.
2 November 2023, 5:13 pm