## 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 pm## lvps1000vm:

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 pm## Tanya Khovanova's Math Blog » Blog Archive » More Gnomes:

[…] « Shapovalov’s Gnomes […]

19 June 2022, 10:37 am## Tanya 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