MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 72 characters in body

As a bit of fun, I have written a program that attempts to fit the first n rectangles into the square. (I accept that this is not an obvious route to a proof.)

Initially, I planned to jumble the rectangles without any strategy, except that I constrained each new rectangle to share a vertex with at least one previous rectangle. Unfortunately, I quickly found that backtracking is extremely time-consuming. In retrospect, this makes sense: if a state is reached where there are only N spaces big enough to accept the next (N+1) rectangles, backtracking will probably need to try all (N!) permutations before deciding to backtrack further. (And this is as it should be, because one of the permutations may free up a corner to allow progress.) So, without strategy, 255 rectangles go in and then there is no more progress for a long time in this algorithm: Dead end

So, I added a bit of strategy: try to make as many edge-to-edge joins as possible. With this algorithm, I have reached 40000 (and still going) without any need at all for backtracking. (In fact, it's quite rare to find an exact fit into a gap, where a new rectangle has edge-to-edge contact with three existing rectangles. Therefore, in retrospect, it would probably be roughly as good to insist that new rectangles have two or more edge-to-edge contacts -- which will effectively mean fitting into "corners" where the new rectangle fills the only remaining quadrant at a vertex.)

Here's an image of the situation after 10000 rectangles: Maximized_contact. There is a different pattern, arguably just as good, if the first position with 2 edge-to-edge contacts is selected: Two_contacts (after 1000 rectangles). This is quicker.

For the squeamish, look away now: I have been using floating-point arithmetic. With the gcc compiler's somewhat lame "long double", this stores about 20 decimal places. So, I have insisted that an "exact" contact must have coordinates that match to at least 19 decimal places. A "clear" gap or overlap between non-contacts must be at least, say, 10^-13 10^-14 -- so there are six 5 orders of magnitude between "presumably touching" and "presumably separate". You could regard this as having a probabilistic chance of a mistake, and I guess (without justification) the probability might be of order 10^-610^-5.

If gaps are required to be at least 1e-12, then the algorithm is unsure whether (1/3912 + 1/4124 - 1/4050 - 1/3981) is zero or gap-- this is a . If gaps are at least 1e-13, the same happens with (1/26981+29981-14201). These are real exampleexamples, and it's easy to concoct other situations that would challenge higher precision. (For example, try 1/30234+1/26811-1/28672-1/28172.) So far, no in-between gaps (between 1e-19 and 1e-131e-14) have been encountered.

I have recently started checking the results using arbitrary-length rational numbers (using the IMath package). This is slower, of course. The size of the denominator could be excessive (see A003418), but only 138 base-10 digits were required up to 4800 rectangles. This took about 5 hours on a desktop. The code isn't designed for efficiency, and gets progressively slower in a variety of ways.

It may seem pointless to press on beyond 1000, or 2000 or whatever, and it probably is. However, there is an exciting crunch point at about 17000: until this point, there has been a clear region of unfilled space, substantially larger than the incoming rectangles. Any rectangle that doesn't fit conveniently elsewhere can go in there. This is quite a luxurious position: you can tell at a glance that deadlock won't be reached in the next few placements. When that space is filled, are the remaining slivers large enough? -- the rectangles aren't small enough that remaining gaps look like wide-open spaces. Initial experience suggests that this crunch is survived, but of course there may be more crunches to come.

Here are images: Wide open space at 10000 and Impending crunch at 15000, Crunch at 17000 (zoomed in) and Crunch averted so far, at 30000

@Kevin Buzzard: I hope this doesn't take the fun out of your interactive applet. I think you're right that a bit of insight comes out of this square-bashing: there is hope that there are enough small rectangles to more or less fill the gaps between medium rectangles, and enough really small rectangles to more or less fill the gaps between small rectangles, and so on. This seems to be the hope, rather than clever arrangements of exact matches.

I can be specific about the rarity of filling exact matches using this algorithm: 20 three-edge contacts in the first 1000 rectangles, 6 in the next, and 4 in the next. Presumably more could be arranged by thinking ahead. Also, a better algorithm could do a lot more to avoid small gaps (which must be the killer in the end, if there is a killer).

show/hide this revision's text 1

As a bit of fun, I have written a program that attempts to fit the first n rectangles into the square. (I accept that this is not an obvious route to a proof.)

Initially, I planned to jumble the rectangles without any strategy, except that I constrained each new rectangle to share a vertex with at least one previous rectangle. Unfortunately, I quickly found that backtracking is extremely time-consuming. In retrospect, this makes sense: if a state is reached where there are only N spaces big enough to accept the next (N+1) rectangles, backtracking will probably need to try all (N!) permutations before deciding to backtrack further. (And this is as it should be, because one of the permutations may free up a corner to allow progress.) So, without strategy, 255 rectangles go in and then there is no more progress for a long time in this algorithm: Dead end

So, I added a bit of strategy: try to make as many edge-to-edge joins as possible. With this algorithm, I have reached 40000 (and still going) without any need at all for backtracking. (In fact, it's quite rare to find an exact fit into a gap, where a new rectangle has edge-to-edge contact with three existing rectangles. Therefore, in retrospect, it would probably be roughly as good to insist that new rectangles have two or more edge-to-edge contacts -- which will effectively mean fitting into "corners" where the new rectangle fills the only remaining quadrant at a vertex.)

Here's an image of the situation after 10000 rectangles: Maximized_contact. There is a different pattern, arguably just as good, if the first position with 2 edge-to-edge contacts is selected: Two_contacts (after 1000 rectangles). This is quicker.

For the squeamish, look away now: I have been using floating-point arithmetic. With the gcc compiler's somewhat lame "long double", this stores about 20 decimal places. So, I have insisted that an "exact" contact must have coordinates that match to at least 19 decimal places. A "clear" gap or overlap between non-contacts must be at least, say, 10^-13 -- so there are six orders of magnitude between "presumably touching" and "presumably separate". You could regard this as having a probabilistic chance of a mistake, and I guess (without justification) the probability might be of order 10^-6.

If gaps are required to be at least 1e-12, then the algorithm is unsure whether (1/3912 + 1/4124 - 1/4050 - 1/3981) is zero or gap -- this is a real example, and it's easy to concoct other situations that would challenge higher precision. (For example, try 1/30234+1/26811-1/28672-1/28172.) So far, no in-between gaps (between 1e-19 and 1e-13) have been encountered.

I have recently started checking the results using arbitrary-length rational numbers (using the IMath package). This is slower, of course. The size of the denominator could be excessive (see A003418), but only 138 base-10 digits were required up to 4800 rectangles. This took about 5 hours on a desktop. The code isn't designed for efficiency, and gets progressively slower in a variety of ways.

It may seem pointless to press on beyond 1000, or 2000 or whatever, and it probably is. However, there is an exciting crunch point at about 17000: until this point, there has been a clear region of unfilled space, substantially larger than the incoming rectangles. Any rectangle that doesn't fit conveniently elsewhere can go in there. This is quite a luxurious position: you can tell at a glance that deadlock won't be reached in the next few placements. When that space is filled, are the remaining slivers large enough? -- the rectangles aren't small enough that remaining gaps look like wide-open spaces. Initial experience suggests that this crunch is survived, but of course there may be more crunches to come.

Here are images: Wide open space at 10000 and Impending crunch at 15000, Crunch at 17000 (zoomed in) and Crunch averted so far, at 30000

@Kevin Buzzard: I hope this doesn't take the fun out of your interactive applet. I think you're right that a bit of insight comes out of this square-bashing: there is hope that there are enough small rectangles to more or less fill the gaps between medium rectangles, and enough really small rectangles to more or less fill the gaps between small rectangles, and so on. This seems to be the hope, rather than clever arrangements of exact matches.

I can be specific about the rarity of filling exact matches using this algorithm: 20 three-edge contacts in the first 1000 rectangles, 6 in the next, and 4 in the next. Presumably more could be arranged by thinking ahead. Also, a better algorithm could do a lot more to avoid small gaps (which must be the killer in the end, if there is a killer).