Wikipedia:Reference desk/Archives/Mathematics/2019 August 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 11

Why do there exist minimal square containing n squares of side length 1?

I have a question on Square packing in a square. Let us say n>0 is a given integer. How do we know that there is a minimal square that contains n squares of side length 1 having no common interior points? I think this follows from compactness but I was unable to find suitable theorem that implies the result.--85.76.4.140 (talk) 18:04, 11 August 2019 (UTC)

Short answer: yes. Slightly longer, hand-wavy sketch of a proof: Each square can be specified by the location of its center and its orientation. Topologically, this data is the space $\mathbb {R} ^{2}\times S^{1}$ ($S^{1}$ is a circle, although we're thinking of it scaled since a square rotated by a quarter of a circle will be back to its original state). Thus, a configuration of n squares can be described by the subspace of $(\mathbb {R} ^{2}\times S^{1})^{n}$ that corresponds to valid (ie, non-overlapping squares) configurations. And really, we dont need to consider all of $\mathbb {R}$ here to describe the squares' centers; just pick a large enough value of M and use [0,M] so that all the squares have plenty of room to move around each other freely. So our space is now the subspace of valid configurations of $([0,M]^{2}\times S^{1})^{n}.$ This subspace is closed (this is really the most technical part of the proof; it's not deep, but it takes some work to show), and hence compact.

Then, you can just consider the function which maps a point in this space to the size of the containing square corresponding to the given configuration. This is a continuous function (again, some work to show this, but it's believable if you think about it). So the image of this function is therefore compact itself, and has a minimum value. –Deacon Vorbis (carbon • videos) 19:31, 11 August 2019 (UTC)

A slight simplification (imo) is to instead prove there is a maximum size of the small squares so they all fit in a large square of length 1, then apply a similarity to get the small squares to have size 1. That adds some dimensions to the configuration space but it's now compact to start with and there's no need to throw in the M. Also, all the constraints can be written in the form (continuous function of the configuration space)≥0, so the subset satisfying each one is closed and ∴the intersection is closed. The argument is very general, so it applies to any similar question like what the smallest size of shape Y that contains non-overlapping areas of shape X, for any basic geometric shapes X and Y -- squares, triangles, circles, half-moons, etc. Note that the argument does not work, and indeed the statement is not true, if you required the shapes to not touch instead of merely not overlap. --RDBury (talk) 23:23, 11 August 2019 (UTC)

I would actually say that the short answer is "no" per your argument... I would assume the compactness argument the OP had in mind was in line with "consider the set $S_{n}=\{x\geq 0|{\text{n squares fit with no overlap within a square of size }}x\}$; it has a lower bound in reals", which is insufficient. (The problem is that we do not know whether that set is topologically closed, which is necessary to conclude "hence that set is compact and the lower bound belongs to it".) Tigraan^{Click here to contact me} 08:08, 12 August 2019 (UTC)

I'm not sure what you're getting at here. We're not arguing that the set is compact because it is closed but that it is closed because it is compact. Actually S_n as you defined it not bounded above so it's not compact. Deacon Vorbis' work around for this is to pick a large M and let S_n,M = {x: 0≤x≤M, n squares fit with no overlap within a square of size x} which is fine as long as you pick M large enough that S_n,M is non-empty. What I was saying is you can get around using the M by considering T_n = {x: 0≤x, n squares of side x fit with no overlap within a square of size 1} and proving T_n is a closed interval. (I'm taking 0∈T_n by defining a square of side 0 to be a point.) In either case the argument is to say the set is the continuous image of a compact set, i.e. the space of feasible configurations, therefore it's compact, therefore closed, and therefore contains the endpoint we're interested in. In case it's not clear above, I'm taking the word 'overlap' here to mean having an intersection with positive area. I don't what compactness theorem the OP had in mind but the argument presented does seem like the natural way to go and it does use compactness. --RDBury (talk) 15:07, 13 August 2019 (UTC)

The (insufficient) argument I presented was what jumped to my mind when reading the OP's handwaving towards compactness, so I wanted to dispel it, but I might have created more confusion than I solved. Tigraan^{Click here to contact me} 16:02, 13 August 2019 (UTC)