22 Oct
2003
22 Oct
'03
6:33 a.m.
At 12:40 PM 10/22/03 +0100, Jon Perry wrote:
Although a different packing allows for 1..8 to be placed in a 15x15 sqtare. Is 2n-1 a upper bound then too?
No; you can show fairly easily that squares of sides 1..9 cannot fit in a square of side 17. The key lemma is that the three squares of sides 5, 6, and 7 cannot be packed into a 9x17 rectangle. The bound even fails numerically, when we get up to ten squares. The sum of the first ten squares is 385, which is bigger than 19x19. Note that the sum of the first n squares is a cubic, n^3/3 + n^2/2 + n/6. Therefore, the minimum side of a square in which they can be packed must increase faster than linear. The best you can hope for is a 3/2 power. -A