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?


ANSWERS

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
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

(George Sicherman)
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

(Bryce Herdt)
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.