¿Este problema de empaquetado tiene siquiera una solución óptima?

Question

En esta respuesta pregunta el usuario Bruno Joyal:

Puede que sea una pregunta ingenua, pero... ¿cómo sabemos que hay es ¿la mejor solución posible?

Yo (pero sólo soy yo) supongo que podría estar pensando en la posibilidad lógica de que exista una secuencia de soluciones cada vez mejores, pero que el límite en sí no sea una solución. Pero, si lo es o no, no importa del todo. Asi que, aqui va...

¿Puede demostrarse que existe una solución óptima?

¿Qué tamaño de cuadrado necesitas para albergar once cuadraditos?

Ni siquiera conozca si esta es la mejor [solución] posible.

YouTube

Answer 1

El espacio de configuración puede representarse como un conjunto compacto, especificando para cada cuadrado la posición de una esquina y el ángulo de rotación, así como el tamaño del cuadrado grande (que puede suponerse delimitado por alguna constante ridículamente grande). Las restricciones son todas de la forma $f(\omega) \ge c$ donde $\omega$ es la configuración y $f$ es una función continua, y el objetivo (el tamaño del gran cuadrado) es una función continua. Así que sí, el mínimo existe.