2740: Square Packing

|< < Prev Comic #2740 (February 20, 2023) Next > >|

Square Packing

Title text: I also managed to improve the solution for n=1 to s<0.97, and with some upgrades I think I can hit 0.96.

Explanation

This explanation may be incomplete or incorrect: Created by a HYDRAULIC PRESSED SQUARE - This appears to be referring to a specific puzzle that merits explanation before going into description of the comic. Do NOT delete this tag too soon. If you can address this issue, please edit the page! Thanks.

The square packing problem is a type of geometry problem. The goal is to find the smallest possible "outer square" that will fit N "inner squares" that are each 1 unit wide and 1 unit tall. In the comic N=11, leading to its name of "The N=11 Square Packing Problem," and the value 's' is the length of the outer square's sides. Whilst sometimes the value of 's' can be precisely known, in the true problem (and in this comic and its title-text, jokingly) sometimes we only know how small it has been so far proven that it can be; there may turn out to be an even smaller valid value, pending further analysis (or pressing) and so inequality notation is used to convey only that it is definitely less than a given number.

A few days before this comic's post, a web page Squares in squares gained interest on social media platforms such as Twitter and Hacker News. For many values of N, that page depicts the best known solutions, some of them known to be optimum. The one for N=11 (best known but not proven to be optimum) is shown on the left here; its general arrangement was found by Walter Trump in 1979 and slightly improved by Gensane et al. in 2004.

Munroe claims to have found a more efficient solution for this N=11 case, by physically deforming the squares involved in the best-known solution with a hydraulic press. The size of the resulting bounding square is indeed smaller, but the "solution" isn't actually one because the inner shapes have countless wrinkles and are no longer squares. Geometrical shapes in packing problems are not conventionally assumed to be deformable in this manner.^{[citation needed]}

The title text mentions the same approach "improved" the solution for 1 unit square, whose optimum solution is obviously that unit square itself with s=1. Munroe remarks that if he had "some upgrades", presumably a more powerful hydraulic press, he could get the resulting square to be even smaller.

The humorous implication behind the comic and the title text is that rather than the shapes being mathematical, abstract shapes, they are actually physical squares, constructed of some extremely strong, but not completely incompressible material. It is not obvious what material that might be: even using a hydraulic press, its volume can only be reduced to 0.97 or 0.96 times its starting volume. (The fact that the squares exist in a 2D universe in the problem statement, but are being crushed presumably by a 3D hydraulic press is not addressed, either).

This is perhaps a related joke to 2706: Bendy, but now with squares and compressed areas instead of triangles and extended lengths.

‎

Transcript

This transcript is incomplete. Please help editing it! Thanks.

[11 squares optimally packed inside a square arrangement]

Previous best

s<3.877084

(Gensane, 2004)

[11 deformed squares crushed together to pack them into a smaller square arrangement]

New record

s<3.40

[Caption below the panel:]

I've significantly improved on the solution to the n=11 square packing problem by using a hydraulic press.

 add a comment! ⋅  add a topic (use sparingly)! ⋅  refresh comments!

Discussion

I suspect Randall saw the same social media post that I did (or maybe a repost of the same social media post, who knows or cares). I don't really want to make an explanation, but anyone who does, here's a link to a bunch of square packing findings... of course, no hydraulic press allowed for these packings. https://erich-friedman.github.io/packing/squinsqu/ Tsumikiminiwa (talk) 22:07, 20 February 2023 (UTC)

Yeah, this was on r/mathmemes the other day. 172.64.238.48 00:03, 21 February 2023 (UTC)

Welcome to the Hydraulic Press Channel. Today we have a set of squares that are usually used in packing problems. You are supposed to fit them into other squares by arranging them. But I think we can get them to fit easier if we put them on the press, and just try to make them smaller. We are going to start with one square, and see how much smaller we can make this. And here we go.

Needs to include a mention of the "Square Packer Five Meeellion"... 172.68.51.141 16:48, 21 February 2023 (UTC)

The post where I saw this said: “God is dead, and what killed him was learning [the similarly inelegant-appearing n=17 solution].” 172.70.254.216 13:08, 21 February 2023 (UTC)

172.70.54.77 19:26, 21 February 2023 (UTC) Welcome to the Hydraulic Press channel

What does "s<" mean? Kev (talk) 22:54, 21 February 2023 (UTC)

"S" (the size of the square, within which lie the N small squares) is less than the following number. i.e. that any S of that amount or greater is more than enough space to contain N unit squares. But it isn't fully established what the smallest value of S is, just that it will not be bigger than (or equal to) that provisional limit.

(Do we need a wikilink to inequality notation in the explanation, then? Maybe you can tell us, Kev.) 172.71.242.191 23:17, 21 February 2023 (UTC)

Please! I came to the discussion to ask that an explanation of what s means. I did have a look in the Wikipedia article about it, but they don't use it there. So an explanation in the text with perhaps a link to something that expands on the explanation would be greatly appreciated by me :-) 172.70.91.198 12:45, 22 February 2023 (UTC)

Added something about this. Seems too wordy and partly a repeat of the above. Future editors will refine, no doubt. 141.101.98.77 19:43, 22 February 2023 (UTC)

Well, I had added it. Someone rewrote it and it now just says something not at all what the above people wanted it to say... Go figure... 172.70.90.35 01:10, 23 February 2023 (UTC)

Is there a solution to the problem of the smallest explanation into which n explanations can be packed? 172.70.90.35 11:29, 23 February 2023 (UTC)

Probably, that's [one of] the issue[s] addressed by compression algorithms. 172.70.114.88 23:26, 26 February 2023 (UTC)

I think I saw this new solution in a paper authored by USPS et al. 108.162.216.159 23:33, 21 February 2023 (UTC)

I believe we can get S<3.32 for this problem... if it will Blend. --172.69.79.133 09:28, 22 February 2023 (UTC)

Assuming that when Randall says "some upgrades", he means the strongest hydraulic press humanity has created, what would be the compressive strength of the square in the title text? ~ Megan ^she/_her ^talk/_contribs 01:57, 23 February 2023 (UTC)

First time I've seen a citation in an Explain XKCD explanation, LOL! And if I haven't read all 2740 up until here, I'm close (MAYBE the first few hundred I skipped the explanation if I understood the comic). :) NiceGuy1 (talk) 05:07, 26 February 2023 (UTC)

I'm on mobile so can't easily edit it myself but I think the reference to 11 square packing in 2765: escape speed should be linked to here :) 162.158.34.23 11:37, 29 September 2023 (UTC)