Problem of the Month (June 2015)

The September 2006 Math Magic problem investigated ways to pack copies of a polyomino P in a rectangle so that there was exactly 1 path from the upper left corner to the lower right corner that avoided copies of P. This month we investigate a similar problem. We want to pack red and blue copies of a polyomino in a rectangle so that there are exactly n paths avoiding red squares, and exactly n paths avoiding blue squares. For a given polyomino P and positive integer n, what is the smallest number of copies of P needed? What if there were k colors instead of 2?

ANSWERS

Solutions were received from George Sicherman, Joe DeVincentis, Johannes Waldmann, and Bryce Herdt. Here are the best known answers:

Smallest Known Solutions for 2 Colors
P \ n123456

(George Sicherman)

(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)

(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman) 		?
(George Sicherman)
? ?

(George Sicherman)
(George Sicherman)

(Johannes Waldmann)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
?
(George Sicherman) 		?
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
? ? ? ?
? ? ?
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman) 		? ?
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

P \ n789101112

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman) 		?

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
? ? ?
(Bryce Herdt)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
?
(George Sicherman) 		?
(George Sicherman)
?
(George Sicherman)
(Jonathan Waldmann)
(George Sicherman)
?
(George Sicherman) 		? ? ?
(George Sicherman)
?
(George Sicherman) 		? ? ?
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman) 		?
(George Sicherman)
(George Sicherman)
(George Sicherman)
?
(George Sicherman) 		?
(George Sicherman) 		?
(George Sicherman)
? ? ? ? ? ?

Smallest Known Solutions for 3 Colors
P \ n123456

(George Sicherman)
(George Sicherman)
? ? ? ?
(George Sicherman)
? ? ? ? ? ?
? ? ? ? ? ?

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