2740: Square Packing

2023-02-22T06:01:54Z

Rborchert: /* Explanation */

{{comic
| number = 2740
| date = February 20, 2023
| title = Square Packing
| image = square_packing_2x.png
| imagesize = 326x295px
| noexpand = true
| titletext = 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==
{{incomplete|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.}}
The {{w|Square packing in a square|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 s is the length of the outer square's sides.

A few days before this comic's post, a web page [https://erich-friedman.github.io/packing/squinsqu/ ''Squares in squares''] gained interest on social media platforms such as [https://twitter.com/KangarooPhysics/status/1625436240412540928 Twitter] and [https://news.ycombinator.com/item?id=34809023 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.<ref>Gensane, T., Ryckelynck, P. – ''Improved dense packings of congruent squares in a square''. Discrete Comput Geom 34, pages 97–109 (2005). https://doi.org/10.1007/s00454-004-1129-z</ref>

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 {{w|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.

‎<references />

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:[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.

{{comic discussion}}
[[Category:Math]]
[[Category:Geometry]]

explain xkcd - User contributions [en]

2740: Square Packing