22 Oct
2003
22 Oct
'03
6:06 a.m.
Wed, 22 Oct 2003 12:32:43 +0100 "Jon Perry" <perry@globalnet.co.uk> This MPQ talk is similar to a problem I had considered - what is the smallest square needed to house all 1..n squares? e.g. with 1x1, we need a 1x1 square with 1x1 and 2x2, we need a 3x3 square with 1x1, 2x2 and 3x3, we need a 5x5 square. So a lower bound is 2n-1. However with all the squares from say 1 to 8, this packing fails. It may be that I am off because I am on the road and just waking up, but this strikes me as a loose lower bound, since the _absolute_ minimum is sqrt(n*(n+1)*(2n+1)/6), and this is clearly not achievable for n>1. So any lower bound should be at least on the order of n^1.5.