Erich's Packing Center!

March 17, 2023 10:33 PM

You want squares in triangles? Erich's got 'em! You want triangles in squares? Erich's got 'em! Squares in squares?? Erich's got those, too! How about L's in circles? Triangles in circles? Right triangles in squares? You know Erich's got 'em! Packing! Tiling! Covering! Come on down to Erich's Packing Center for all this and related problems!
posted by Lirp (16 comments total)

The smallest triangles found to cover the squares-in-triangles case are the same size for both the 14-square and 15-square cases and yet the packing arrangement shown for the 14-square case is not simply the 15-square case with one square left out, which suggests to me that those could be the basis for quite a good little puzzle.
posted by flabdablet at 1:05 AM on March 18, 2023 [5 favorites]

:[O])
posted by nightcoast at 3:58 AM on March 18, 2023 [1 favorite]

Square packing #17 made the rounds about a month ago because it's just so chaotic. Like really, this is the best, this jumble of random angles? I'm a little curious how the proof that this is optimal works.
posted by Nelson at 7:38 AM on March 18, 2023 [3 favorites]

This gives me flashbacks of working in a crowded warehouse.

What do the numbers mean?

s = 2 + 2 / √3 = 3.154+

Or,

s = 4 + 10 / √3 = 9.773+

Are these found out using something like matlab, or just by pencil/graph paper?

This is a ripe problem with ML, init?
posted by alex_skazat at 8:16 AM on March 18, 2023

JFC the n=24 case here makes my brain itch with how almost-ly it fits.
posted by nebulawindphone at 8:23 AM on March 18, 2023 [3 favorites]

Randall Monroe has some improvements on the square packing methods.
posted by tdismukes at 8:31 AM on March 18, 2023 [2 favorites]

Man I love packing problems. I wish I had a slightly better head for actually exploring them, but they always produce such wonderful weirdness when you get outside of the well-behaved symmetrical cases, and so many known best solutions are in that weird chaotic space.

That #17 Nelson mentions is sort a perfect example: what a weird mess, and it's not just that it's weird and works, it's that it's weird and nobody knows a better way. Of which:

I'm a little curious how the proof that this is optimal works.

My impression is that in general most of these don't have an actual proof of optimality; they're just the best anyone's found. I gather it's hard to come up with a real analytical proof of any given bounded packing problem, so in most cases for these things it's more a running tally of the best anyone has managed to find for any given specimen for n in any given X's in a bounded Y framework, unless and until someone else finds a better one.

Proofs around them are probably more for certain trivial cases (like there's probably a real simple one for why you can't beat the current solution for a single unit cube in an equilateral triangle) and then proofs about things like best known upper or lower bounds with which people can restrict somewhat the search space for the more out-there large-n cases.
posted by cortex at 8:32 AM on March 18, 2023 [2 favorites]

What do the numbers mean?

s = 2 + 2 / √3 = 3.154+

In this case they're saying s is the length of the side of the bounding object. So the equilateral triangle bounding your set of n squares in the first link in the post: each square is a unit square, side length 1; the goal is to find the smallest known side length s for the bounding equilateral triangle that can accommodate those n unit squares.

So for n = 1, the result is: s = 1 + 2 / √3 = 2.154+

Which is to say, the side length of that triangle with one unit square inside is (as is reasonably easy to follow visually for that case) 1 unit—the length of that bottom edge of the unit square— plus 2 over sqrt(3), which is the side length of an equilateral triangle of height 1. Which, hey, there's the two halves of an equilateral triangle chilling out to either side of that unit square in the n=1 diagram: nice easy visual proof!

You can do the same basic process for any of the other specimens where the bottom edge of the bounding triangle is totally flush with a snug row of unit squares: n= 2, 4, 7, 11, etc. And there's a similar well-behaved if slightly different calculation for the specimens that have a nice three-fold rotational symmetry to them in the same vein of construction: n=3, 6, 9, 15, even 18 where you can ignore those extra three squares stranded in the middle because they aren't packed tight enough to affect that outer border.

Where I personally get into "uh, yeah but HOW did you calculate that" territory is the oddball shit like n=8, 12, 17, where suddenly we're packing in an extra square or two in a funkier alignment that's not directly on an edge. It's for me both a question of how they got that packing and what the actual geometric construction for it is that they're getting the value out of. Which is probably still reasonably straightforward if you're limber on your geometry/trigonometry, but is a little farther than I can go without stretching first and getting a running start.

(But also, look closer at 8, 12, 17: they're all weird, but they're all weird in the same way: there's clearly One Weird Trick that they're each doing, just with more squares tacked on. This is the kind of place where having one good idea might turn into a bunch of new best-known solutions: try that wobbly-square construction vs. some previous best-known slightly cleaner looking packing, and anywhere your wobble trick produces a smaller value of s, you've got a winner! Until someone finds a new weirder way to supplant some of those, etc. Packing problem solutions are speedrun records for geometry.)
posted by cortex at 8:49 AM on March 18, 2023 [3 favorites]

Oh you're right cortex; many of these solutions are best-known. A few are annotated "proved"; #10 is the most complex of squares-in-squares proven. And I think you're right that the finite nature of these problems makes proofs difficult. I wonder if there's even a proof of a lower bound on s other than the obvious one.

JFC the n=24 case here makes my brain itch with how almost-ly it fits.

I think the rendering is making this look closer than it really is? Honestly that diagram makes it look like if you just shook the tray a bit it'd all fall into alignment. But look in the upper right quadrant; they're matching three length 1 sides with two length √2 sides; the three are 6% bigger than the two. You can see where they cheat (the bottom triangle of the three is tucked under the middle one), maybe that's just what 6% looks like.
posted by Nelson at 9:08 AM on March 18, 2023 [1 favorite]

Also, a more approachable game to play with this if, like me, you feel rusty-or-worse about actually comprehending the stickier math involved: just go hunting through these solutions for cases that are clearly just "add another so-so row to an existing solution". Because in the spirit of those three different "just use this one trick" sets I mentioned above, a lot of the slightly more complex-looking solutions on the squares-in-triangle pages are secretly just that: a simpler solution from smaller n plus a bunch of squares in a row.

For example: look at n=5. It's a row of two squares sitting on top of a row of three squares. The upper row of two are flush with their corners against the edges of the bounding triangle; the bottom three are less snug. What happens if you just erase those bottom three and pretend the triangle's bottom edge is against those upper two snugs squares? You get precisely the solution for n=2.

Which means you can get 5 this way: Take n=2, add a 1-unit-high trapezoid to the bottom, and see how many squares you can fit in. Answer is three, and not particularly snug: the diagram there is just one especially tidily symmetric choice among a boringly infinite number of ways you can slightly differently arrange those three squares flat in that lower trapezoid. No arrangement of those three is any better than another: it's all just "we can fit three squares down here, and we sure can't fit four."

So n=5 is really just n=2 plus a loosely-packed 1-height trapezoid.

Similar vibe: look at n=6 and n=10. Same basic idea: n=10 is just n=6 plus a loosely-packed height-1 trapezoid with four squares. Ditto n=9, 14, 20: take a packing, add a trapezoid, and then add ANOTHER trapezoid.

There's more variations to find if you go looking. Again, you have one good new idea and you might get a bunch of new bests out of it. And in a lot of cases solutions that look a little messy or loose or asymmetrical are, fundamentally, just very simple solutions plus n other loosely packed blocks, placed fairly arbitrarily, because there's not enough room to fit n+1 in.

Which gets back to the real weird stuff: based on all of the above, you can reckon that n=3,6,9,12 might be a really consistent pattern. And for 3, 6, and 9 it is, but, wtf 12? The original obvious solution there would definitely have been just a rotationally symmetrical set of three rows of four blocks nestled together in the same fashion. (And in fact, look at n=13: it's exactly that, plus an extra loose block in the middle). Dollars to donuts that that page originally had exactly that with "Found by Erich Friedman in 1997." underneath.

But then along comes David W. Cantrell in July 2002, saying, okay, but check this shit out. He found a new trick. And in fact we've got the same trick and the same caption for other specimens: n=8, 12, 17...hey, that's that same family of slightly weirder packings I mentioned above.

n=1..36 on this page are all Friedman and Cantrell: Friedman's original set of pretty good ideas, plus Cantrell's one weird trick improving a few cases. It's very possible all of those solutions are in fact optimal! It's possible all of them might even be provably so: for smaller n putting together a good proof for a single case or a well-defined subset may be a lot more accomplishable than providing a general proof of optimality for all or very many or very large specimens n. But it's also possible someone will take a hard look at one of these at some point and be like "okay, but check thiiiiiis shit out".
posted by cortex at 9:28 AM on March 18, 2023 [2 favorites]

Also, if you want a little bit of reasonably approachable discussion of all this, here's a writeup by Erich Friedman ca. 2009 on the general territory and recent history of the squares-in-squares packing problem. Returning to the idea of best examples vs. actual proofs above, here's a paragraph that I can't help but read as legitimately slightly catty:

The number of claims far outweighs the number of published results in this area. Göbel says that Schrijver claims that Bajmóoczy proved s(7)=s(8)=3 [7]. Walter Stromquist claimed to have proved s(6)=3 and s(10)=3+1/√2, and claimed to know how to prove s(14)=s(15)=4 and s(24)=5 [13]. Trevor Green sent me a proof for s(6)=3. None of these proofs were published. Said El Moumni evidently proved s(7)=s(8)=3 and s(15)=4 [12] but no one was aware of this until recently. Finally, in 2002, Kearney and Shiu published a proof of s(6)=3 [9].

In other words: a lot of people talking shit, not so many showing their work. Which is hardly unique to mathematics, but it brings me a small, probably unhealthy joy to see a little sass show up in a paper.
posted by cortex at 9:54 AM on March 18, 2023 [3 favorites]

Pretty sure this gets really difficult in higher dimensions.
posted by newdaddy at 12:56 PM on March 18, 2023

Why are there so many gaps in the squares in squares page?
posted by indexy at 1:13 PM on March 18, 2023

That's what this bit at the top is about:

For the n not pictured, the trivial packing (with no tilted squares) is the best known packing.

Which is saying that, basically, whenever you've got a case with an obvious boring solution and no better solution than that, they're not gonna bother to illustrate it.

Look for example at n=6, 7, 8, 9 (which is the last point on the page where that disclaimer doesn't apply): at n=6, you've got two rows of three squares and a gap above, and they haven't found any way to make that bounding square smaller. So it's a very boring, trivial solution: make the bounding square 3x3, stack some squares neat, that it. But it's the same for n=7: two neat stacks plus a square. n=8: same plus two squares. n=9: super trivial, it's literally a square number and it's a perfectly dense 3x3 packing.

So they're saying: hey, and so on and so forth. They don't show twelve because it is, implicitly, just three stacks of four squares in an s=4 bounding square. By this logic they could have also omitted 13 and 14 but I'm guessing they included them to be illustrative of the pattern. And 20-23 are missing because it's the same thing for an s=5 bounding square; they included s=24 to be polite/illustrative.

After that they omit all of 30-36 (a 5x6 stack growing into a perfect 6x6 packing) and 42-49, and so on. Which is why a list of the first hundred packings ends at 89: 90-100 is just an enumeration of the stretch from a 9x10 stack in an s=10 square up through a perfect 10x10.

But if someone can come up with something that fills in one of those gaps, it'll get its own specimen. However, according to that paper in my previous comment, the lowest known example of violating that pattern is for an s =~ 17 bounding square, and it feels unlikely anyone's gonna find something for n < 100 if they haven't already since it's the low-hanging fruit that probably everybody who takes a serious whack at this problem ends up having a go at.
posted by cortex at 1:37 PM on March 18, 2023 [1 favorite]

Ah, I missed that bit at the top. Thanks for the clarification!
posted by indexy at 1:41 PM on March 18, 2023

Honestly that diagram makes it look like if you just shook the tray a bit it'd all fall into alignment. But look in the upper right quadrant; they're matching three length 1 sides with two length √2 sides; the three are 6% bigger than the two.

Right, I mean, obviously it couldn't all just fall into alignment, that's not how irrational numbers work — but the smallness of the difference is infuriating, in that "bouncing screensaver image that never quite lands in the corner" sort of way.
posted by nebulawindphone at 2:36 PM on March 18, 2023