Problem of the Month (April 2000)

Packing non-overlapping unit squares into the smallest possible square is an interesting problem. It is not completely solved, but there has been much recent progress. For example, here is a paper of mine on the subject published as a dynamic survey in the Electronic Journal of Combinatorics.

This month's problem is this: If you are pack n squares of one size and m squares of another (possibly equal) size inside a unit square, what is the largest area they can cover? What about using more than 2 sizes of squares?

ANSWERS

Define S(n,m) to be the maximum area that n squares of one size and m squares of another size can cover in a packing of a unit square.

Brendan Owen and all the solvers noted that if n, m, or n+m is square, then S(n,m)=1. Also, If there are positive integers a, b and c such that m/a2 and n/b2 are integers which add to c2, then S(n,m)=1.

Joseph DeVincentis gave packings for n,m ≤ 11, which were mostly optimal.

Trevor Green gave packings for n ≤ 20 and m ≤ 5, which were mostly optimal.

Ulrich Schimke gave packings for n,m ≤ 5, which were mostly optimal.

Green and Schimke independently conjectured that if 0 ≤ k ≤ n2, then S(n2–1,k) = 1 – (1–S(0,k))/n2 unless S(n2–1,k) = 1. That is, the n2–1 squares should have length 1/n. But this is not true for many pairs.

David Cantrell improved several of my packings in 2007.

Maurizio Morandi improved several packings in 2012 and 2014.

Here are the best known lower bounds for S(n,n).

Largest Area Covered by n Squares of Two Sizes


S(1,1) = 1
S(2,2) = 1
S(3,3) = 15/16 = .9375
S(4,4) = 1

S(5,5) ≥ 125/144 = .868+
S(6,6) ≥ .862+
S(7,7) ≥ 35/36 = .972+
S(8,8) = 1

S(9,9) = 1
S(10,10) ≥ 65/72 = .902+
S(11,11) ≥ 187/200 = .935
S(12,12) ≥ 24/25 = .960

S(13,13) ≥ 377/392 = .961+
S(14,14) ≥ 35/36 = .972+
S(15,15) ≥ 255/256 = .996+
S(16,16) = 1

S(17,17) ≥ 221/225 = .982+
 
S(18,18) = 1
 
S(19,19) ≥ 247/256 = .964+
(David Cantrell)
S(20,20) = 1
 

S(21,21) ≥ 609/625 = .974+
 
S(22,22) ≥ 286/289 = .989+
(Maurizio Morandi)
S(23,23) ≥ .982+
(Maurizio Morandi)
S(24,24) ≥ 624/625 = .998+
 

S(25,25) = 1
 
S(26,26) ≥ 221/225 = .982+
 
S(27,27) ≥ 74/75 = .986+
(Maurizio Morandi)
S(28,28) ≥ 952/961 = .990+
(Maurizio Morandi)

S(29,29) ≥ 5945/6084 = .977+
 
S(30,30) ≥ 39/40 = .975
(Maurizio Morandi)
S(31,31) ≥ 775/784 = .988+
(Maurizio Morandi)
S(32,32) = 1
 

S(33,33) ≥ 583/588 = .991+
 
S(34,34) ≥ .991+
(Maurizio Morandi)
S(35,35) ≥ 1295/1296 = .999+
 
S(36,36) = 1
 

S(37,37) ≥ 481/484 = .993+
(Maurizio Morandi)
S(38,38) ≥ 950/961 = .988+
(David Cantrell)
S(39,39) ≥ 195/196 = .994+
 
S(40,40) ≥ 80/81 = .987+
 

S(41,41) ≥ 3485/3528 = .987+
(Maurizio Morandi)
S(42,42) ≥ 119/120 = .991+
(Maurizio Morandi)
S(43,43) ≥ 1075/1089 = .987+
(Maurizio Morandi)
S(44,44) ≥ 440/441 = .997+
 

S(45,45) = 1
(David Cantrell)
S(46,46) ≥ 391/392 = .997+
 
S(47,47) ≥ 1222/1225 = .997+
 
S(48,48) ≥ 2400/2401 = .999+
 

S(49,49) = 1
 
S(50,50) = 1
 
S(51,51) ≥ 255/256 = .996+
 
S(52,52) = 1
(Maurizio Morandi)

S(53,53) ≥ 3233/3249 = .995+
(Maurizio Morandi)
S(54,54) ≥ 1836/1849 = .992+
(Maurizio Morandi)
S(55,55) ≥ 2035/2048 = .993+
(Maurizio Morandi)
S(56,56) ≥ 340/343 = .991+
(Maurizio Morandi)

S(57,57) ≥ 471/475 = .991+
(Maurizio Morandi)
S(58,58) ≥ 2378/2401 = .990+
(Maurizio Morandi)
S(59,59) ≥ 20591/20736 = .993+
(Maurizio Morandi)
S(60,60) ≥ 255/256 = .996+
 

S(61,61) ≥ .992+
(David Cantrell)
S(62,62) ≥ 1147/1152 = .995+
 
S(63,63) ≥ 4095/4096 = .999+
 
S(64,64) = 1
 

S(65,65) ≥ .990+
(Maurizio Morandi)
S(66,66) ≥ 2860/2883 = .992+
(Maurizio Morandi)
S(67,67) ≥ 1675/1681 = .996+
(Maurizio Morandi)
S(68,68) ≥ 3944/3969 = .993+
(Maurizio Morandi)

S(69,69) ≥ 299/300 = .996+
(Maurizio Morandi)
S(70,70) ≥ 6230/6241 = .998+
(Maurizio Morandi)
S(71,71) ≥ 4331/4356 = .994+
(Maurizio Morandi)
S(72,72) = 1
 

S(73,73) ≥ 25769/25921 = .994+
(Maurizio Morandi)
S(74,74) ≥ 10249/10368 = .988+
(Maurizio Morandi)
S(75,75) ≥ 3250/3267 = .994+
(Maurizio Morandi)
S(76,76) ≥ 323/324 = .996+
(Maurizio Morandi)

S(77,77) ≥ 6545/6561 = .997+
(Maurizio Morandi)
S(78,78) ≥ 3445/3456 = .996+
(Maurizio Morandi)
S(79,79) ≥ .996+
(Maurizio Morandi)
S(80,80) = 1
 

S(81,81) = 1
 
S(82,82) .994+
(Maurizio Morandi)
S(83,83) ≥ 8051/8100 = .993+
(Maurizio Morandi)
S(84,84) ≥ 1365/1369 = .997+
(Maurizio Morandi)

S(85,85) ≥ 1445/1458 = .991+
(Maurizio Morandi)
S(86,86) ≥ 1247/1250 = .997+
(Maurizio Morandi)
S(87,87) ≥ 3161/3174 = .995+
(Maurizio Morandi)
S(88,88) ≥ 440/441 = .997+
(Maurizio Morandi)

S(89,89) ≥ 48149/48400 = .994+
(Maurizio Morandi)
S(90,90) = 1
 
S(91,91) ≥ 9919/10000 = .991+
 
S(92,92) ≥ 391/392 = .997+
(Maurizio Morandi)

S(93,93) ≥ 2697/2704 = .997+
(Maurizio Morandi)
S(94,94) ≥ 799/800 = .998+
 
S(95,95) ≥ 323/324 = .996+
 
S(96,96) ≥ 2400/2401 = .999+
(Maurizio Morandi)

S(97,97) ≥ 8633/8649 = .998+
(Maurizio Morandi)
S(98,98) = 1
 
S(99,99) ≥ 9999/10000 = .999+
 
S(100,100) = 1
 

Here are the best known lower bounds for S(n,m). Click on the values for pictures.

Largest Area Covered by Squares of Two Sizes

n \ m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 1
2 1 1
3 1 7/8 15/16
4 1 1 1 1
5 1 13/16 .920+ 1 125/144
6 1 8/9 1 1 74/81 .862+
7 1 1 17/18 1 11/12 17/18 35/36
8 1 1 35/36 1 .964+ 26/27 1 1
9 1 1 1 1 1 1 1 1 1
10 1 29/32 .931+ 1 15/16 1 43/45 .969+ 1 65/72
11 1 .855+ .932+ 1 1 49/50 211/225 .970+ 1 139/144 187/200
12 1 7/8 24/25 1 19/20 1 17/18 120/121 1 23/24 .932+ 24/25
13 1 15/16 1 1 137/144 71/75 115/121 47/48 1 71/72 63/64 1 377/392
14 1 1 31/32 1 61/64 31/32 63/64 1 1 39/40 1 53/54 109/112 35/36
15 1 31/32 63/64 1 .980+ 47/48 71/72 143/144 1 1 .983+ 145/147 253/256 127/128 255/256
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
17 1 1 19/20 1 113/121 249/256 80/81 1 1 .962+ 61/64 311/324 .957+ 143/144 .985+ 1 221/225
18 1 1 .943+ 1 117/121 24/25 1 1 1 162/169 31/32 35/36 27/28 1 .985+ 1 1 1
David Cantrell
Maurizio Morandi

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