Problem of the Month (September 2006)

In the 2002 World Puzzle Championship, there was a puzzle in the form of a rectangular grid containing several 1×1 and 2×2 squares. The puzzle was to find the unique path from the top left to the bottom right of the grid that intersected each 2×2 square in exactly one square and didn't pass through any of the dark 1×1 squares. Can you solve this puzzle?

Although not a terribly hard puzzle, it got me (as a puzzle designer) thinking about how hard it was to produce such a puzzle without those pesky dark squares. In particular, given a polyomino P, and a non-negative integer n no greater than the area of P, what is the smallest rectangular puzzle containing some non-overlapping copies of P that has a unique path connecting opposite corners that intersects each copy of P in exactly n squares? We do not allow the path to start or end inside a copy of P.

What are the answers for the tetrominoes? Can you prove that many of the cases, especially with large n, are impossible? What about larger polyominoes? Is there a solution for every polyomino and n=1? Can you classify the polyominoes that have solutions where n is equal to the area of the polyomino? Can you classify the polyominoes that fail to have solutions for n=0?

ANSWERS

Sam Collins wrote a C++ program to solve the World Championship puzzle:

Here are the smallest known solutions for polyominoes of area 5 or less.

Small Polyominoes
P \ n 0 1 2 3

Tetrominoes
P \ n 0 1 2 3 4
?
?
?
? ?

Pentominoes
0 1 2 3 4 5
? ?
? ?
? ?
? ?
? ? ?

(Sune Kristian Jakobsen) 		? ? ?
? ?
? ?
? ? ?
? ?
? ?

(Sune Kristian Jakobsen) 		? ? ?

All of the hexominoes have puzzles for n=0 using either 1 or 2 copies of P. Sune Kristian Jakobsen found the last case. They also all have solutions for n=1 using 1 or 2 copies of P. Most of them have solutions for n=2, but I couldn't find solutions for these:

Thanks to Gabriele Carelli for finding a solution for one of these. The only ones I found that needed more than 2 copies of P were these. Can you improve any of them?


(Sune Kristian Jakobsen)
Sune Kristian Jakobsen found there are 9 heptominoes that need more than 2 copies of P, and 2 that have no solutions for n=0. Here are the smallest known solutions. Can you improve any of them?


(Sune Kristian Jakobsen)

(Sune Kristian Jakobsen)
(Sune Kristian Jakobsen)
(Corey Plover)


(Berend van der Zwaag)

Sune Kristian Jakobsen thinks that this polyomino had no unique paths for any value of n.

Sune Kristian Jakobsen also sent an analysis of which polyominoes had unique paths for n equal to their area. The answer is more complicated than I thought.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 9/25/06.