¿Puede caber un número finito de cuadrados, con área total como máximo 1, en un cuadrado de área 2?

Question

Parece ser un teorema que un número finito de cuadrados, con área total a lo sumo 1, se puede encajar en un cuadrado con área 2 sin superposiciones. Estoy buscando una prueba de esto.

Google me llevó a esta respuesta mathoverflow (véase el corolario 1). Pero no entiendo la respuesta -- en particular no puedo seguir la prueba del "lema de empaquetamiento" en la respuesta.

¿Puede alguien explicar la prueba del lema de empaquetamiento que se da en esa respuesta, o dar otra prueba del mismo, o indicarme alguna otra prueba de la pregunta del título?

Answer 1

Se trata del teorema de Moon-Moser, J W Moon y L Moser, Some packing and covering theorems, Colloq. Math. 17 1967 103-110, MR0215197 (35 #6040). También es el Problema 80 en Bela Bollobas, The Art of Mathematics; véanse las páginas 194-196 para la solución.

Janusz Januszewski, Empaquetamiento de rectángulos en el cuadrado unitario, Geom Dedicata 81 (2000) 13-18, MR1772192 (2001d:52029) generaliza el resultado: toda secuencia de rectángulos puede empaquetarse en el cuadrado unitario siempre que su área total sea como máximo $1/2$ y sus longitudes laterales son como máximo $1$ .

Answer 2

La prueba a la que has enlazado es sencilla, pero algo confusa, ya que utilizan $c$ para representar tanto la dimensión del rectángulo original como la dimensión del mayor cuadrado restante. También existe, como has observado, un caso que se pasa por alto.

La idea de la prueba es utilizar la hipótesis de inducción para cubrir más de $1/2$ del área de rectángulos más pequeños cortados de $R$ hasta que la parte restante de $R$ tiene una superficie inferior a $c^2$ y teniendo en cuenta que $c\times c$ subrectángulo estaba completamente cubierto más de la mitad de $R$ está cubierto.

He aquí un intento de aclarar la prueba:

Lema de empaquetamiento. Sea $R$ ser un $c$ por $b$ rectángulo, $c\le b$ y $F$ sea un conjunto finito de cuadrados cuya área total sea al menos la mitad del área de $R$ y el cuadrado mayor de tamaño $c$ . Entonces un subconjunto de $F$ que contiene el $c$ cuadrado se puede empaquetar en $R$ de forma que cubra al menos la mitad de la superficie de $R$ .

Si $F$ contiene sólo un cuadrado entonces el lema es obviamente cierto ya que podemos encajar en $R$ y tiene más de la mitad de superficie. Así que procedamos por inducción. Primero recortamos un cuadrado de lado $c$ . Ahora dejemos que $c'$ sea el cuadrado más grande que quede. Si es posible cortar una tira de altura $c'$ del resto de $R$ (haciendo un rectángulo de tamaño $c\times c'$ ), hágalo. Ahora, o bien los cuadrados que quedan en $F$ tienen un área superior a la mitad de la banda, en cuyo caso podemos cubrir más de la mitad de la banda con cuadrados de $F$ por la hipótesis de inducción, entonces volvemos y cortamos otra tira, etc., o los cuadrados restantes tienen un área menor que la mitad del área de la tira, en cuyo caso podemos encajarlos todos en un sub rectángulo que tenga el doble de su área por la hipótesis de inducción, y ya está, ya que el área total de $F$ era al menos la mitad de la superficie de $R$ y hemos encajado todos los cuadrados. Cuando el cuadrado mayor que queda es mayor que el resto de $R$ hemos terminado. Todas las tiras excepto la última están llenas más de la mitad, pero el primer cuadrado está completamente lleno (es el cuadrado de lado $c$ ) y la tira restante tiene una superficie menor que el cuadrado de lado $c$ (tiene anchura $c$ y altura inferior a $c$ ) para que todo el rectángulo quede cubierto hasta la mitad.