Problem of the Month (October 2018)

In the November 2002 Math Magic, we studied matrices of distinct positive integers with the property that each row had constant sum and each column had constant product. This month we generalize to allow some entries to be blank. We call any such shape a sum-product polyominoes or SPP. Below are the only known SPP's with 6 or 7 entries (up to permutations of rows and columns). We show them labeled with the smallest possible entries (by sum or product):

321
1410
204
33
1896
1122
41012
1565
234108
543627
124
8125
1510
163224
4219254
288
228
525
219
30

What shapes can a SPP with 8 or more entries have? What are the smallest possible entries?


ANSWERS

Solutions were sent by Joe DeVincentis and Lewis Chen.

Here are the known shapes of SPP's with the smallest known entries:

6
41012
1565

26 / 60
33
1896
1122

33 / 198
321
1410
204

24 / 840

7
234108
543627

117 / 108
124
8125
1510

25 / 120
163224
4219254
288

288 / 12,096
228
525
219
30

30 / 6300
60
4020
1050
1248

60 / 2400 (JD)

8
2101220
30653

44 / 60
30
101532
6420

30 / 60
205
64312
1015

25 / 60
12116
41015
524

29 / 240
110
56
83
92

11 / 360
50070
5673
30540
45525

570 / 283500 (LC)
96
6036
1590
3264

96 / 5760 (JD)

9
234660
30201510

75 / 60
90
8163036
1452420

90 / 720 (JD)
51030
201186
936

45 / 180
83218
63616
4819

58 / 288
11015
1268
2042

26 / 240
1614
1218
246
282

30 / 672
2412
12114
2826
36

36 / 1008
640
2836
451
1630

46 / 1440
436
832
1525
2416
40

40 / 460,800

10
28123040
60151043

92 / 120
271812
236469
543

57 / 108
161220
510159
363

39 / 180
6018
1221045
30336

69 / 360
24
13155
6108
204

24 / 120
24
1545
6810
2013

24 / 120
31215
41016
2820
30

30 / 240
28
15103
21214
1720

28 / 840
244
10216
12115
820

28 / 960

SPP's do not have to be connected. Are these the smallest possible product and sum?

247244070105140168280
4202101203521128653
840

840 / 840 (JD)
9080608
161824180
14445409
103236160

238 / 1440

Theorem: If a SPP has a singleton column, it must have at least 3 other columns.
Proof: Say a column contains only the number n. Since the numbers must all be different, and each column has product n, the two largest numbers besides n are at most n/2 and n/3, which total less than n. (Joe DeVincentis points out this also proves that every other row besides the singleton column must contain at least 3 entries.)

Theorem: A SPP cannot contain singleton column and a singleton row unless it is the same singleton.
Proof: If a row only contains the number n, then because the row sums are constant, every other number in the SPP is smaller than n. This means the column that only contains one number cannot have product at least n.

Theorem: A SPP cannot contain two singleton columns or two singleton rows.
Proof: This follows directly from the fact that all the numbers need to be different.

Theorem: No SPP can have exactly two numbers in each row and each column.
Proof: (by Joe DeVincentis) Suppose we have a SPP {{A,S–A,,...},{,B,S–B,...},{,,C,S–C,...},...}, and assume without loss of generality that B>C. Their common product implies B(S–A) = C(S–B), or B/C = (S–B)/(S–A). This means S–B>S–A which implies A>B, and working around the chain we reach a contradiction.

Theorem: The only SPP with fewer than 6 numbers is the trivial 1×1 SPP.
Proof: Only a 2×2 SPP avoids a a singleton row or column, and that is impossible by the previous theorem. If there is a singleton column, there must be at least 6 other entries. The only remaining case is {{a,c–a},{b,c–b},{c,}}. But abc=(c–a)(c–b) or abc=c2–ac–bc+ab implies that ab divides c, so ab≥c, so abc≥c2>(c–a)(c–b).

Unknown Cases
7
8
9
(among others)


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