Embalaje de paralelogramos con lados$1$ y$\sqrt{2}$ y ángulo$45^{\circ}$ en un contenedor rectangular

Question

Si $ABCD$ es un paralelogramo tal que $\angle BAD=\frac{\pi}{4}$, $AB=\sqrt{2}$, $AD=1$ entonces podemos decir que $ABCD$ es un buen paralelogramo. Los paralelogramos se pueden girar en cualquier ángulo.

a) Demostrar que en un contenedor rectangular $2 \times n$ ($n \ge 2$) no se llena con más de $2n-2$ buena paralelogramos (el embalaje debe ser sin solapamientos entre los paralelogramos).

b) Demostrar que en un contenedor rectangular $4 \times 4$ no puede ser embalado con más de $12$ buena paralelogramos (el embalaje debe ser sin solapamientos entre los paralelogramos).

De mi trabajo. Es fácil de empacar $2n-2$ buena paralelogramos en contenedor rectangular $2 \times n$. La zona de la buena paralelogramo es $1$. El área del contenedor rectangular $2 \times n$ es $2n$. Obviamente, paralelogramos no será capaz de cubrir todas las regiones del contenedor rectangular. Por lo tanto, en un contenedor rectangular $2 \times n$ ($n \ge 2$) no se llena con más de $2n-1$ buena paralelogramos. Pero no tengo idea de cómo mejorar la evaluación de un paralelogramo.

Answer 1

En general, los problemas de embalaje es un problema muy difícil. Así que, en su caso, el método que recomiendo es probar uno por uno los casos de $2\times 2$, $2\times 3$, $2\times 4$. Entonces usted tiene que probar que para $n\times 2$ con $n\ge 5$, en cada extremo del rectángulo, en el último $2\times 2$-cuadrado no se puede cubrir un área mayor a 0.5 con los paralelogramos, es decir, usted tiene que dejar al descubierto una región (o varias regiones), con el área de mayor a 0.5. Si te las arreglas para probar esto, entonces el resultado de la siguiente manera, para que usted no puede cubrir un área mayor que 1 en el total del rectángulo $n\times 2$, así que usted puede tener un máximo de 2n-2 paralelogramos. Este método directo requiere teniendo en cuenta que muchas posiciones posibles para los paralelogramos. En general hay muchos resultados sobre la densidad asintótica y la densidad de los envases, pero para cada ejemplo concreto el único método para determinar el empaquetamiento óptimo es el análisis de todos los casos posibles. En el caso de $4\times 4$ el problema es aún más difícil, ya que hay mucho más de los casos a considerar.

Podría sospechar que, en general, el empaquetamiento óptimo de un rectángulo con el entero sidelengths $m$ e $n$ con los paralelogramos podría ser realizable con $mn-\min\{m,n\}$ paralelogramos, que encaja muy bien para $(m,n)=(2,n)$ e $(m,n)=(4,4)$ para el problema dado, pero esto no es posible. Probablemente, uno puede demostrar que tal colocación es la óptima entre los envases que tienen cada paralelogramo corte exactamente en la mitad por el número entero cuadrícula formada por la unidad de plazas, pero en general esta no es la mejor de embalaje. Por ejemplo, si $m=22$ e $n=17$, entonces podríamos pack 357 paralelogramos utilizando este método. Pero si hacemos las maletas de los paralelogramos girado 90°, se puede empacar $24\times 15=360$ paralelogramos, lo que muestra que el primer embalaje no es el óptimo.