# Problem of the Month (July 2016)

Given a non-negative integer k, what connected sets of polyominoes on the square grid have the property that each polyomino is horizontally or vertically adjacent to polyominoes that have total area k times its own area? If there is a configuration of polyominoes with certain areas, what is the smallest such configuration?

Solutions were received from Bryce Herdt, Joe DeVincentis, George Sicherman, and Jeremy Galvagni.

Jeremy Galvagni showed that every integer k has at least one solution. In particular, a 1×k2 rectangle can be surrounded by k2 non-touching copies of a 1×k rectangle.

Here are the smallest known configurations for integer values of k:

k=2
 1 2 12 3 13 23 123 4 14 24 124 34 134 234 1234 5

Joe DeVincentis showed that the only numerical configurations where area 6 is the largest area are the ones shown below:
 6 36 246 123456

And then he proved that all such solutions for the k=2 case are just scaled up versions of one of the solutions above. Thus only area sets that are multiples of {1}, {1,2}, {1,2,3}, {1,2,3,4}, and {1,2,3,4,5,6} are possible!

k=3
 1 2 12 3 13 23(Bryce Herdt) 123 4 14 24 124 34 134 234 1234(George Sicherman) 5 15 25 125(Bryce Herdt) 35 135(George Sicherman) 235 1235 45 145 245 1245 345 1345 2345 12345 6

k=4
 1 2 12 3(George Sicherman) 13(Joe DeVincentis) 23(George Sicherman) 123(Maurizio Morandi) 4(George Sicherman) 14(Bryce Herdt) 24 124 34? 134 234(Joe DeVincentis) 1234(Joe DeVincentis) 5 15 25 125(Bryce Herdt) 35 135(Bryce Herdt) 235(George Sicherman) 1235(George Sicherman) 45 145 245(see below) 1245(George Sicherman) 345(George Sicherman) 1345(George Sicherman) 2345(George Sicherman) 12345(George Sicherman) 6

Here is the largest configuration:

245

(Bryce Herdt)

k=5
 5(George Sicherman) 145(George Sicherman) 6 26(Joe DeVincentis)

 36(George Sicherman) 236(George Sicherman) 246(George Sicherman) 1256(George Sicherman) 2356(George Sicherman)

 13456(George Sicherman) 7 8 28

 48 9(George Sicherman) 39 369(George Sicherman) 10

 2 10 2 4 10(George Sicherman) 5 10 1 2 5 10(George Sicherman) 2 5 11(Joe DeVincentis) 1 2 5 11(Joe DeVincentis)
 11(George Sicherman) 12 3 12 4 12 1 5 12
 1 2 5 12(Joe DeVincentis) 3 5 12(George Sicherman) 6 12 2 6 12 1 5 13(Joe DeVincentis) 1 2 5 13(Joe DeVincentis)
 2 5 13(Joe DeVincentis) 14 1 5 14(Joe DeVincentis) 7 14 2 8 10 14(George Sicherman) 5 15(Joe DeVincentis)

k=6
 3 12 5 15

Bryce Herdt noted that only integer k were possible, and suggested that we use non-integral multiples and round. He suggested rounding to the nearest integer, but it is easier to round down to avoid ambiguities. I proved there are only finitely many solutions for k ≤ √2. Does every fractional k have at least one solution?

For 1 < k < 2, here are the only solutions with smallest area n, for small n:

n \ k(1, 5/4)(5/4, 4/3)[4/3, 3/2)[3/2, 5/3)[5/3, 7/4)[7/4, 9/5)[9/5, 11/6)[11/6, 13/7)[13/7, 17/9)[17/9, 19/10)[19/10, 2)
1
2
3
4
(JD)

n \ k(1, 6/5)(6/5, 10/7)[10/7, 11/7)[11/7, 13/8)[13/8, 7/4)[7/4, 16/9)[16/9, 9/5)[9/5, 20/11)[20/11, 17/9)[17/9, 23/12)[23/12, 27/14)[27/14, 29/15)[29/15, 2)
5
(JD)

Here are the smallest known solutions for various fractional values of k:

k = 52 (rounding down)
 1(Bryce Herdt) 2 12 3 13 23 123(Maurizio Morandi) 4 14 24 124 34 134 234 1234(George Sicherman) 5 15 25(George Sicherman) 125 35 135 235 1235(Bryce Herdt) 45 145 245 1245 345 1345 2345 12345 6

k = 72 (rounding down)
 1 2 12 3 13 23(George Sicherman) 123(George Sicherman) 4 14 24 124 34 134(George Sicherman) 234 1234(George Sicherman) 5 15 25 125 35(Bryce Herdt) 135(George Sicherman) 235(George Sicherman) 1235(George Sicherman) 45(George Sicherman) 145 245 1245 345(George Sicherman) 1345(George Sicherman) 2345(George Sicherman) 12345(Bryce Herdt) 6

k = 92 (rounding down)
 23 ? 123 ? 14 ? 34 ? 234 ? 145 ? 345 ? 13(Joe DeVincentis) 124(George Sicherman) 134(Joe DeVincentis) 1234(Joe DeVincentis) 25(George Sicherman)

 125(Joe DeVincentis) 35(George Sicherman) 135(Bryce Herdt) 235(Joe DeVincentis) 1235(Joe DeVincentis) 45(George Sicherman) 245(Joe DeVincentis)

 1245(George Sicherman) 1345(Joe DeVincentis) 2345(George Sicherman) 12345(George Sicherman)

 136(Joe DeVincentis) 56(George Sicherman) 237(George Sicherman) 37 148 12358(George Sicherman)

 13458(George Sicherman) 123458(George Sicherman) 29(George Sicherman) 49 149 249

 359(George Sicherman) 3 4 10(Joe DeVincentis) 2 4 5 10(Joe DeVincentis) 1 4 9 10(Joe DeVincentis) 5 11(George Sicherman) 3 7 11(Joe DeVincentis)

 5 12(George Sicherman) 1 4 13(George Sicherman) 2 5 13(George Sicherman) 1 3 5 8 14(George Sicherman)

k = 73 (rounding down)
 1 2 12 3 13 23 123(George Sicherman) 4 14 24 124 34(George Sicherman) 134 234 1234(George Sicherman) 5 15 25 125 35 135 235 1235 45 145 245 1245 345 1345 2345 12345 6

k = 83 (rounding down)
 1 2 12(George Sicherman) 3 13 23(George Sicherman) 123(Bryce Herdt) 4 14 24 124 34(George Sicherman) 134 234 1234(George Sicherman) 5 15 25(George Sicherman) 125 35(George Sicherman) 135 235 1235(Bryce Herdt) 45(George Sicherman) 145 245 1245(Joe DeVincentis) 345 1345 2345(Bryce Herdt) 12345(Bryce Herdt) 6

k = 103 (rounding down)
 1 2 12 3 13(George Sicherman) 23 123 4 14 24 124 34 134(Bryce Herdt) 234(George Sicherman) 1234(George Sicherman) 5 15 25 125 35 135(Bryce Herdt) 235(George Sicherman) 1235(George Sicherman) 45 145 245(George Sicherman) 1245(Bryce Herdt) 345(Bryce Herdt) 1345(George Sicherman) 2345(Bryce Herdt) 12345(Bryce Herdt) 6

k = 113 (rounding down)
 1 2 12 3 13 23 123(Bryce Herdt) 4 14 24 124 34 134(Bryce Herdt) 234(Bryce Herdt) 1234(George Sicherman) 5 15 25 125 35(George Sicherman) 135(George Sicherman) 235(George Sicherman) 1235(George Sicherman) 45 145 245 1245(Bryce Herdt) 345(Bryce Herdt) 1345(George Sicherman) 2345(George Sicherman) 12345(George Sicherman) 6

k = 133 (rounding down)
 34 ? 45 ? 345 ? 13(Joe DeVincentis) 23(George Sicherman) 123(George Sicherman) 14 124(George Sicherman)

 134(Joe DeVincentis) 234(Joe DeVincentis) 1234(George Sicherman) 125(George Sicherman) 35 135(Joe DeVincentis)

 235(Joe DeVincentis) 1235(Joe DeVincentis) 145 245(Joe DeVincentis) 1245(Joe DeVincentis) 1345(Joe DeVincentis) 2345(Joe DeVincentis)

 12345(George Sicherman) 1236(George Sicherman) 1246(Joe DeVincentis) 2356(Joe DeVincentis) 37(George Sicherman) 247(Joe DeVincentis) 1257(Joe DeVincentis)

 367(George Sicherman) 28(George Sicherman) 138(George Sicherman) 1238(George Sicherman) 1248(Joe DeVincentis)

 58(George Sicherman) 139(Joe DeVincentis) 269(George Sicherman) 3 10(Joe DeVincentis)

 1 3 11(George Sicherman) 2 4 11(Joe DeVincentis) 1 4 12(Joe DeVincentis) 2 8 12(George Sicherman)

k = 143 (rounding down)
 13 ? 23 ? 14 ? 34 ? 134 ? 234 ? 1234 ? 125 ? 35 ? 135 ? 235 ? 45 ? 145 ? 245 ? 1245 ? 345 ? 1345 ? 2345 ? 123(Joe DeVincentis) 124(Joe DeVincentis) 25(George Sicherman) 1235(Joe DeVincentis)

 12345(George Sicherman) 1246(George Sicherman) 137(George Sicherman) 27(George Sicherman) 247(George Sicherman) 38(Joe DeVincentis)

 368(George Sicherman) 149(George Sicherman) 29(George Sicherman) 249(George Sicherman) 4 10(Joe DeVincentis)

 1 4 6 10(George Sicherman) 3 11(Joe DeVincentis) 2 3 9 11(George Sicherman) 4 6 12(George Sicherman) 5 13(Joe DeVincentis)

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