7
$\begingroup$

Under this answer, user Bruno Joyal asks:

This might be a naive question, but... how do we know there is a best possible solution?

I (but that's just me) assume that he might be thinking of a logical possibility that there is a sequence of ever better solutions, but that the limit itself is not a solution. But, whether he is or not doesn't quite matter. So, here goes...

Can it be proven that there exists an optimal solution?

How big a square do you need to hold eleven little squares?

enter image description here

We don't even know if this is the best possible [solution.]

YouTube

$\endgroup$
0

1 Answer 1

Reset to default
11
$\begingroup$

The configuration space can be represented as a compact set, specifying for each square the position of one corner and the angle of rotation, as well as the size of the big square (which can be assumed to be bounded by some ridiculously large constant). The constraints are all of the form $f(\omega) \ge c$ where $\omega$ is the configuration and $f$ is a continuous function, and the objective (the size of the big square) is a continuous function. So yes, the minimum does exist.

$\endgroup$
6
  • 3
    $\begingroup$ Is it obvious that the configuration space is compact? Seems like this is really the heart of the question. $\endgroup$
    – Bruno Joyal
    Nov 26, 2013 at 18:47
  • 2
    $\begingroup$ Yes, $[0,R]^n \times [0,2\pi]^n$ is compact. $\endgroup$
    – Robert Israel
    Nov 26, 2013 at 19:07
  • 3
    $\begingroup$ As for the constraints, note that the area of overlap of two squares is a continuous function of the configuration. $\endgroup$
    – Robert Israel
    Nov 26, 2013 at 19:17
  • $\begingroup$ Thanks! When I said "configuration space", I meant the subset where the constraints of the problem are satisfied. I am convinced now! $\endgroup$
    – Bruno Joyal
    Nov 26, 2013 at 19:31
  • $\begingroup$ @BrunoJoyal Good enough for me (although it did require some thinking of my own). If you concur, I'll accept this answer. [Edit: I missed your last comment. I'll accept.] $\endgroup$
    – Řídící
    Nov 26, 2013 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .