Shapovalov’s Gnomes
Here is another lovely problem from a prolific problem writer, Alexander Shapovalov.
Problem. Every cell of a 7 by 7 chessboard has a gnome standing on it. For every pair of gnomes whose cells share an edge, their beards’ lengths differ by no more than 1 inch. Now, we take these gnomes and sit them around a table. Prove that we can do so in a way that any two gnomes sitting next to each other have their beards’ lengths differ by no more than 1 inch.
A standard chessboard is 8 by 8. Why would this problem have a 7 by 7 board? Let’s see.
For even-sized boards, the problem is easy. I will explain why, but first, let me construct a graph related to a board, in this case, any board.
Each cell is a vertex, and two vertices are connected by an edge if the corresponding cells are orthogonal neighbors (share an edge) on the board. A cycle that goes through a graph and visits every vertex exactly once is called a Hamiltonian cycle. A Hamiltonian cycle is a potential way to sit the gnomes around the table and solve the problem. When we sit the gnomes in a circle following a Hamiltonian cycle, two neighbors at the table are also neighbors on the board, and so they have their beards’ lengths differ by no more than 1 inch.
The problem is easy for even-sized boards because it is easy to draw a Hamiltonian cycle on them. An odd-sized chessboard can’t have a Hamiltonian cycle. To prove this, let me color the board in a checkerboard manner. Then, cells that share an edge are different colors. And you can’t make a cycle through the board, where you switch colors at each step, but the total number of steps is odd.
It follows that for odd-sized boards, it is impossible to solve the problem by just connecting neighboring cells on the board. There should be another way. Can you find it?
Share:
Anatoly:
Let
11 June 2022, 10:35 am1 2
3 4
be the upper left corner of the board. We can draw a Hamiltonian cycle through all the cells except the corner cell 1, so that the cycle goes: … 3 4 2 … If 1 is close to 4 we can just insert it on either side of 4, so suppose 1 > 4 by more than 1 inch. Then 2 and 3 are both larger then 4 and smaller than 1. We can put either 1 or 4 between 2 and 3 equally well, so we just need to find a place for the other one. If the cell coming before 3 in the cycle is smaller than 3, we can insert 4 between them, and if it’s larger, we can insert 1 between them, so the final order will be … 1 3 4 2… or …. 4 3 1 2….
Grant:
Great puzzle! There are lots of nice variations of “domino tiling of a square board” type problems.
You might enjoy a classic quant finance interview question “can you pack 53 bricks of dimensions 1x1x4 into a 6 x 6 x 6 box?” See section 2.3 of Xinfeng Zhou’s “A practical guide to quantitative finance interviews” (https://usermanual.wiki/Document/Practical20Guide20To20Quantitative20Finance20Interview.604244935.pdf) for an answer.
11 June 2022, 9:24 pmlvps1000vm:
Draw an arbitrary cycle including a longest-bearded and a shortest-bearded gnome and sit them around a table. All left out gnomes have a beard equally long as an already seated gnome, so add them to the table next to someone with the same length.
13 June 2022, 1:19 pmTanya Khovanova's Math Blog » Blog Archive » More Gnomes:
[…] « Shapovalov’s Gnomes […]
19 June 2022, 10:37 amTanya Khovanova's Math Blog » Blog Archive » Brick Puzzle:
[…] reading my post, Shapovalov’s Gnomes, Grant, one of my readers, directed me to the Brick puzzle from Section 2.3 of Xinfeng Zhou’s […]
4 July 2022, 11:43 am