¿Cuántas galletas hay en la caja de galletas? - Azulejos de estrellas

19

Con la próxima temporada de vacaciones, decidí hacer algunas estrellas de canela . Eso fue divertido (y el resultado sabroso), pero mi nerd interno se encogió cuando puse la primera bandeja de estrellas en la caja y no cabían en una capa:

ingrese la descripción de la imagen aquí

¡Casi! ¿Hay alguna forma en que podrían haber encajado? ¿Qué tan bien podemos enlosar las estrellas, de todos modos? Dado que se trata de estrellas regulares de seis puntas, sin duda podríamos usar las conocidas inclinaciones hexagonales como una aproximación, así:

ingrese la descripción de la imagen aquí
Desordenado el de la esquina superior derecha, ¡vaya!

¿Pero es esto óptimo? Hay mucho espacio entre las puntas.

Para esta consideración, limitémonos a cajas rectangulares y estrellas regulares de seis puntas, es decir, hay treinta grados (o π6 6 ) entre cada punta y sus rincones vecinos. Las estrellas se caracterizan por el radio internoy el radio externo:ryoro

ingrese la descripción de la imagen aquí
[ fuente ]

Tenga en cuenta que tenemos hexágonos para y hexagramas para . Creo que es razonable considerar estos extremos (para las cookies) y restringirnos al rango intermedio, es decir, .ryo=32roryo=13roryor0 0[13,32]

Mis cookies tienen y ignorando las imperfecciones. ¡Iba por gusto, no por una vez!ryo17metrometroro25metrometro

¿Cuál es un mosaico óptimo para las estrellas como se caracterizó anteriormente? Si no hay un mejor mosaico estático, ¿hay un algoritmo para encontrar uno bueno de manera eficiente?

Rafael
fuente
1
Sí, lo sé: ¿qué has intentado y dónde te has atascado? Este es solo un lindo "problema" en la vida real que pensé que sería divertido pensar en la temporada de galletas, especialmente para aquellos que son pensadores en lugar de panaderos. ¡Que te diviertas!
Raphael
44
Presumiblemente te quedaste atascado en el glaseado. En la cocina. * rimshot *
David Richerby

Respuestas:

15

Déjame responder tu pregunta parcialmente para el caso del hexagrama.

Puedes hacer el siguiente mosaico

ingrese la descripción de la imagen aquí

Con esto, cubrirá 12/14 = 6/7 del plano (cuente los triángulos en el cuadrilátero discontinuo).

¿Es esto óptimo? Yo creo que si. Aunque no estoy dando una prueba, proporcionaré algunos argumentos. Uno puede preguntar, qué tan bueno podemos llenar el espacio (triángulo) entre las puntas puntiagudas. En el mosaico anterior, llenamos la mitad. ¿Podemos hacerlo mejor?

ingrese la descripción de la imagen aquí

segundo2(X)23bronceado(X)+2.

La trama de esta función se ve así y muestra que nuestra intuición era correcta.

ingrese la descripción de la imagen aquí

A.Schulz
fuente
0

Lo siguiente no se ofrece como un ataque definitivo o específico / superior sobre este problema posiblemente inesperadamente complejo, sino como ángulos científicos / teóricos / estudios generales adicionales no cubiertos hasta ahora.

1 st esta área general se conoce / clasificado como "embalaje bin" y este es un caso 2d. Hay algunas pruebas famosas de las matemáticas que están relacionadas, por ejemplo, el caso 3D de la investigación de Keplers sobre el empaque de esferas, que fue un problema abierto durante siglos y que Hales resolvió "recientemente" con pruebas informáticas. Un ejemplo de caso 2D que se utiliza a diario en la industria es para optimizar el diseño de los chips. Obviamente, esto es diferente del problema, pero puede señalar algo de la complejidad de este tipo de problemas. por ejemplo, no parece haber ninguna teoría que requiera / indique que un caso 2d sería más simple que un caso 3d. También tenga en cuenta que un límite rectangular simple no necesariamente ayuda a simplificar la solución aparte de decir, un límite poligonal.

podría haber una solución analítica posible si se proporcionara algún tipo de definición / esquema básico de "mosaico regular" en el enunciado del problema, como la colocación en una cuadrícula, etc.

Las condiciones del problema (tal vez contraintuitivamente) no parecen conducir a una solución analítica óptima. Esto puede sorprender a algunos, pero se sabe que los problemas muy similares de alicatar el avión son indecidibles (este fue un resultado famoso hace años y hay muchas referencias e incluso investigaciones en curso). Una diferencia clave entre los problemas decidibles (solucionables / analíticos) e indecidibles es si el mosaico es "regular". el problema anterior se refiere a "estrellas regulares" pero no se refiere a "mosaico regular". la otra respuesta actual supone una especie de mosaico u orden regular, pero tenga en cuenta que incluso definir "mosaico regular" puede ser muy complicado formal / matemáticamente.

problemas como este son generalmente bastante susceptibles a los algoritmos genéticos . dicho algoritmo puede encontrar empaquetamientos "muy buenos" que es poco probable que se mejoren mucho, y tal vez se puedan establecer algunos límites en su optimización mediante métodos muy ingeniosos (es decir, deben estar dentro de un pequeño porcentaje de error del óptimo), pero no pueden probar ninguno Son óptimos.

Aquí hay algunas referencias encontradas que generalmente son directamente aplicables:

vzn
fuente
teoría similar ver también tetraedros de embalaje de Chang / NYT. conjetura (algo inspirado en el artículo): para este problema específico, existe un empaque irregular que es superior a cualquier otro normal.
vzn
0

Si bien este problema en particular probablemente no se ha estudiado, Laszlo Fejes Toth ha hecho estas preguntas y se conocen como problemas de empaque. Recomiendo encarecidamente el tercer capítulo del libro de Pach-Agarwal .

domotorp
fuente
1
Tal como están las cosas, esta no es una respuesta sino un comentario. ¿Puede resumir lo que contiene el libro citado sobre el asunto y cómo puede aplicarse aquí?
Raphael