Problem of the Month (May 2012)

How can a integer-sided square be packed with smaller distinct integer-sided squares with the smallest waste? For small n, the best packing of square with side n is by squares of sides n-1 and 1, with waste 2n. But for larger n, we can do better. What are the best packings for larger n? What if squares are replaced with almost squares, rectangles of the form n×(n+1)?


ANSWERS

Richard Sabey, Joe DeVincentis, George Sicherman, and Berend van der Zwaag sent solutions.

For small n, the best packing of square with side n is by squares of sides n-1 and 1, with waste 2n.

Squares in Squares
15

waste=21
17

waste=29
18

waste=20
19

waste=25
20

waste=30
21

waste=12 (JD) (GS)
22

waste=19
23

waste=24
24

waste=17
25

waste=13 (JD)
26

waste=13
27

waste=18 (GS)
28

waste=14
29

waste=19 (JD)
30

waste=14
31

waste=15 (GS)
32

waste=15
33

waste=15
34

waste=20 (GS)
35

waste=15
36

waste=20 (GS)
37

waste=16
38

waste=22 (GS)
39

waste=16 (BZ) (GS)
40

waste=16
41

waste=17 (GS)
42

waste=21 (BZ)
43

waste=22 (GS)
44

waste=17 (GS) (JD)
45

waste=13 (GS)
46

waste=22 (GS)
47

waste=20 (GS)
48

waste=26 (GS)
49

waste=18 (GS)
50

waste=19 (GS)
51

waste=17 (GS)
52

waste=15 (GS)
53

waste=16 (GS)
54

waste=20 (GS)
55

waste=12 (GS)
56

waste=16 (GS)
57

waste=4 (GS)
58

waste=14 (GS)
59

waste=8 (GS)
60

waste=18 (GS)
61

waste=8 (GS)
62

waste=18 (GS)
63

waste=12 (GS)
64

waste=17 (GS)
65

waste=15 (GS)
66

waste=16 (GS)
67

waste=22 (GS)
68

waste=6 (GS)
69

waste=18 (GS)
70

waste=20 (GS)
71

waste=13 (GS)
72

waste=20 (GS)
73

waste=17 (GS)
74

waste=25 (GS)
75

waste=4 (GS)
76

waste=20 (GS)
77

waste=10 (GS)
78

waste=16 (GS)
79

waste=27 (GS)
80

waste=17 (GS)


For small n, the best packing of an n×(n+1) almost square is by squares of sides n and 1, with waste n-1.

Squares in Almost Squares
11

waste=10
12

waste=11
13

waste=12
14

waste=6
15

waste=14
16

waste=12
17

waste=6
18

waste=6
19

waste=10
20

waste=4
21

waste=6
22

waste=5
23

waste=9
24

waste=4
25

waste=5
26

waste=2
27

waste=11
28

waste=3
29

waste=2
30

waste=2
31

waste=8
32

waste=0
33

waste=6
34

waste=6
35

waste=9 (GS)
36

waste=4
37

waste=6
38

waste=5
39

waste=8
40

waste=4 (JD)
41

waste=4 (GS)
42

waste=5 (GS)
43

waste=11 (JD)
44

waste=3 (JD)
45

waste=9 (JD)
46

waste=9 (JD)
47

waste=8 (JD)
48

waste=7 (JD)
49

waste=9 (JD)
50

waste=9 (JD)
51

waste=4 (JD)
52

waste=7 (JD)
53

waste=12 (GS)
54

waste=17 (GS)
55

waste=17 (GS)

Richard Sabey told me that the only other squares in almost squares with waste=0 smaller than n=100 are the ones below:

80

waste=0
96

waste=0
97

waste=0


For small n, the best packing of an n×n square is by (n-1)×n and 1×2 almost squares, with waste n-2.

Since the area of every almost square is even, the waste has the same parity as n.

Almost Squares in Squares
11

waste=9
12

waste=10
13

waste=1
14

waste=12
15

waste=3
16

waste=0
17

waste=1
18

waste=0
19

waste=1
20

waste=0
21

waste=1 (GS)
22

waste=0
23

waste=1 (GS)
24

waste=0
25

waste=1
26

waste=0 (GS)
27

waste=1 (GS)
28

waste=0
29

waste=1
30

waste=0
31

waste=1
32

waste=0
33

waste=1
34

waste=0
35

waste=1
36

waste=0
37

waste=1 (GS)
38

waste=0 (GS)
39

waste=1 (GS)
40

waste=0
41

waste=1 (JD)
42

waste=0 (GS)
43

waste=1 (GS)
44

waste=0 (GS)
45

waste=1 (GS)
46

waste=0 (GS)
47

waste=1 (GS)
48

waste=0 (GS)
49

waste=1 (GS)
50

waste=0 (GS)

Apparently this trend continues, with the minimum waste being possible for large n.


Since the area of every almost square is even, the waste is always even.

Almost Squares in Almost Squares
6

waste=2
7

waste=6
8

waste=2
9

waste=8
10

waste=0
11

waste=6
12

waste=0
13

waste=4
14

waste=0
15

waste=0
16

waste=2
17

waste=4
18

waste=0
19

waste=2
20

waste=0
21

waste=0
22

waste=0 (GS)
23

waste=0 (GS)
24

waste=0
25

waste=0
26

waste=0
27

waste=0 (GS)
28

waste=0
29

waste=0
30

waste=0
31

waste=0 (GS)
32

waste=0
33

waste=0
34

waste=0
35

waste=0
36

waste=0 (GS)
37

waste=0
38

waste=0
39

waste=0
40

waste=0
41

waste=0 (GS)
42

waste=0 (GS)
43

waste=0 (GS)
44

waste=0 (GS)
45

waste=0 (GS)
46

waste=0 (GS)
47

waste=0 (GS)
48

waste=0 (GS)
49

waste=0 (GS)
50

waste=0 (GS)
51

waste=0 (GS)
52

waste=0 (GS)
53

waste=0 (GS)
54

waste=0 (GS)
55

waste=0 (GS)

Apparently this trend continues, with the waste=0 being possible for large n.


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