Problem of the Month (November 2010)

1. What is the smallest polyomino that has exactly n different Hamiltonian circuits, loops that pass through every square exactly once?

2. What if we change the problem to Hamiltonian paths?

3. Now we tilt polyominoes 45o, and consider downward paths from the unique top square to the unique bottom square. We label every square with the number of such paths passing through it. What is the smallest tilted polyomino containing n squares with the same label, no two of which are on the same path from top to bottom? If so, what are the smallest polyominoes with n squares labeled k?

ANSWERS

Solvers this month include George Sicherman, Berend van der Zwaag, Joe DeVincentis, Dave Langers, and Bryce Herdt.

1.

Bryce Herdt showed that all positive integers have solutions.

The best known answers are shown below:

1
2
3

(GS) 		4
5
6
7
8

(DL)
9
10
11
12

(DL) 		13

(DL) 		14
15

(DL) 		16

(DL) 		17

(DL) 		18

(DL) 		19

(DL) 		20

(DL)
21

(DL) 		22

(DL) 		23

(DL) 		24

(DL) 		25

(DL) 		26

(DL)
27

(DL) 		28

(DL) 		29

(DL) 		30

(DL) 		31

(DL) 		32

(DL)
33

(DL) 		34

(DL) 		35

(DL) 		36

(DL) 		37

(DL) 		38

(DL)
39

(DL) 		40

(DL) 		41

(DL) 		42

(DL) 		43

(DL) 		44

(DL)
45

(DL) 		46

(DL) 		47

(DL) 		48

(DL) 		49

(DL) 		50

(DL)

The best solutions for 51-100 that Dave Langers sent to me in text format can be found here.

George Sicherman is always interested in polyhexes. He sent minimal solutions for some small n before Dave Langers did the first 100:

George Sicherman also showed that solutions for polyiamonds do not exist for n≥2;

2.

The stacks for n=2, n=3, and n=5 show that there is a solution for every value of n. Berend van der Zwaag and Joe DeVincentis noticed that products of two integers can be glued together like n=6 and n=9. Bryce Herdt managed to find constructions that would manage odd n≥17 with n-4 squares and even n≥46 with (n-4)/2 squares. He suspects that these are O(log n).

The best known answers are shown below:

1
2
3
4
5
6

(BZ) 		7

(BZ) 		8

(JD) 		9

(BZ) 		10

(BZ) 		11

(BZ)

12

(JD) 		13

(BZ) 		14

(JD) 		15

(BZ) 		16

(BH) 		17

(BZ) 		18

(BZ) 		19
20
21

(BZ)

22

(JD) 		23

(BZ) 		24

(JD) 		25

(JD) 		26

(BZ) 		27

(BZ) 		28

(BZ) 		29

(BZ) 		30

(JD) 		31

(JD)

32

(JD) 		33

(JD) 		34

(BZ) 		35

(JD) 		36

(BZ) 		37

(BZ) 		38

(JD) 		39

(JD) 		40

(BZ)
41

(BZ) 		42

(BZ) 		43

(BZ) 		44

(JD) 		45

(BZ) 		46

(JD) 		47

(JD) 		48

(JD) 		49

(BZ) 		50

(JD)

George Sicherman furnished solutions for some small polyhexes, and Dave Langers did the rest:

Again, George Sicherman furnished solutions for some small polyiamonds, and Dave Langers did the rest. Dave Langers showed that even n≥12 have solutions no larger than n triangles, and odd n have solutions no larger than 4n-1 triangles. Can anyone improve these bounds?

Dave Langers suggested that this problem (and the preceding one) would be interesting (and hard to program) with collections of tangent circles. For example, here are some solutions for small n:

1
2
3
4
5
6
7
8
10
11
12
14
17

3.

The best known answers are shown below:

1
2
3
4

(JD) 		5

(JD) 		6

(JD)

Joe DeVincentis conjectures that all the smallest tilted polyominoes with n equal numbers are indeed 1's, and that for all n≥6 they take the same form as that of n=3 and n=6. If this is true, what are the smallest polyominoes with n equal numbers of k?

George Sicherman and Joe DeVincentis noticed that adding a k×2 rectangle that overlaps the k=1 solution on top gives a solution for k. Joe DeVincentis showed that these are not always optimal.

What if we remove the restriction that the numbered squares not be on the same path? Joe DeVincentis and Bryce Herdt noticed that a 2×n rectangle with a tail of k–2 squares gives solutions for these.

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