Combien de cookies dans la boîte à cookies? - Étoiles en mosaïque

19

Avec le temps des fêtes qui approche, j'ai décidé de faire des étoiles à la cannelle . C'était amusant (et le résultat savoureux), mais mon nerd intérieur a grincé des dents lorsque j'ai mis le premier plateau d'étoiles dans la boîte et elles ne tenaient pas dans une seule couche:

entrez la description de l'image ici

Presque! Y a-t-il une façon dont ils auraient pu s'adapter? Comment pouvons-nous bien carreler les étoiles, de toute façon? Étant donné qu'il s'agit d'étoiles à six pointes régulières, nous pourrions certainement utiliser les pavages hexagonaux bien connus comme une approximation, comme ceci:

entrez la description de l'image ici
Foiré celui en haut à droite, oups.

Mais est-ce optimal? Il y a beaucoup de place entre les astuces.

Pour cette considération, limitons-nous aux boîtes rectangulaires et aux étoiles régulières à six pointes, c'est-à-dire qu'il y a trente degrés (ou ) entre chaque pointe et ses coins voisins. Les étoiles sont caractérisées par le rayon intérieurriet le rayon extérieurro:π6riro

entrez la description de l'image ici
[ source ]

Notez que nous avons des hexagones pour ri=32rori=13rorir0[13,32]

ri17mmro25mm

Qu'est-ce qu'un carrelage optimal pour les étoiles tel que caractérisé ci-dessus? S'il n'y a pas de meilleur carrelage statique, existe-t-il un algorithme pour en trouver un bon efficacement?

Raphael
la source
1
Oui, je sais: qu'avez-vous essayé et où vous êtes-vous retrouvé coincé? C'est juste un "problème" réel et mignon auquel je pensais qu'il serait amusant de penser pendant la saison des cookies, en particulier pour ceux qui sont des penseurs plutôt que des boulangers. S'amuser!
Raphael
4
Vraisemblablement, vous vous êtes accroché au glaçage. Dans la cuisine. * rimshot *
David Richerby

Réponses:

15

Permettez-moi de répondre partiellement à votre question pour le cas de l'hexagramme.

Vous pouvez faire le carrelage suivant

entrez la description de l'image ici

Par cela, vous couvrirez 12/14 = 6/7 de l'avion (comptez les triangles dans le quadrilatère en pointillés).

Est-ce optimal? Je pense que oui. Bien que je ne donne pas de preuve, je fournirai quelques arguments. On peut se demander à quel point nous pouvons remplir l'espace (triangle) entre les pointes pointues. Dans le carrelage ci-dessus, nous en remplissons la moitié. Pouvons-nous faire mieux?

entrez la description de l'image ici

sec2(x)23tan(x)+2.

L'intrigue de cette fonction ressemble à ceci et montre que notre intuition avait raison.

entrez la description de l'image ici

A.Schulz
la source
0

ce qui suit n'est pas proposé comme une attaque définitive ou spécifique / supérieure sur ce problème peut-être d'une complexité inattendue mais comme des angles scientifiques / théoriques supplémentaires / étude générale non couverts jusqu'à présent.

1 er ce domaine général est connu / classé comme "emballage de poubelle" et c'est un cas 2d. il y a des preuves mathématiques célèbres qui sont liées, par exemple le cas 3D de l' enquête Keplers sur l'emballage des sphères qui était un problème ouvert depuis des siècles et "récemment" résolu avec une preuve informatique par Hales. un exemple de cas 2D utilisé quotidiennement dans l'industrie consiste à optimiser la disposition des puces. évidemment, cela est différent du problème, mais peut indiquer une partie de la complexité de ces types de problèmes. par exemple, il ne semble pas y avoir de théorie qui exige / indique qu'un cas 2d serait plus simple qu'un cas 3d. notez également qu'une simple frontière rectangulaire n'aide pas nécessairement à simplifier la solution autre que, disons, une frontière polygonale.

il pourrait y avoir une solution analytique possible si une sorte de définition / schéma de base de "mosaïque régulière" était donnée dans l'énoncé du problème, comme le placement sur une grille, etc.

les conditions du problème (peut-être contre-intuitivement) ne semblent pas conduire à une solution optimale analytique. cela peut surprendre certains mais des problèmes très similaires de carrelage de l'avion sont connus pour être indécidables (c'était un résultat célèbre il y a des années et il existe de nombreuses références et même des recherches en cours). une différence clé entre les problèmes décidables (résolubles / analytiques) et indécidables est de savoir si le carrelage est "régulier". le problème ci-dessus fait référence aux "étoiles régulières" mais ne fait pas référence au "carrelage régulier". l'autre réponse actuelle suppose une sorte de pavage ou d'ordre régulier, mais notez que même définir un "pavage régulier" peut être très délicat formellement / mathématiquement.

des problèmes comme celui-ci se prêtent généralement assez bien aux algorithmes génétiques . un tel algorithme peut trouver de "très bons" emballages qui ne sont pas susceptibles d'être améliorés de beaucoup, et peut-être que certaines limites peuvent être placées sur leur optimalité via des méthodes très ingénieuses (c'est-à-dire qu'elles doivent se situer dans un petit pourcentage d'erreur optimal), mais ne peuvent en prouver aucune. sont optimales.

voici quelques références trouvées qui sont généralement directement applicables:

vzn
la source
théorie similaire, voir également l' emballage des tétraèdres par Chang / NYT. conjecture (quelque peu inspirée par l'article): pour ce problème spécifique, il existe un emballage irrégulier qui est supérieur à tout emballage régulier.
vzn
0

Bien que ce problème particulier n'ait probablement pas été étudié, de telles questions ont été posées par Laszlo Fejes Toth et sont connues sous le nom de problèmes d'emballage. Je recommande fortement le troisième chapitre du livre Pach-Agarwal .

domotorp
la source
1
En l'état, ce n'est pas une réponse mais un commentaire. Pouvez-vous résumer ce que le livre cité contient à ce sujet et comment il peut s'appliquer ici?
Raphael