La boite de sucre

par **Ben314** » 23 Nov 2009, 16:56

Voici la seconde :

Combien au maximum peut-on mettre de morceaux de sucre de 1x2x4 dans une boite cubique de 10x10x10 ?

(RE)P.S. : J'ai eu la flemme de consulter tout les anciens messages pour voir si cette énigme était déjà présente...

par **nodgim** » 23 Nov 2009, 19:22

Le 125ème, il faudra le casser pour le caser.

par **Ben314** » 23 Nov 2009, 19:28

Tu as la preuve ? (je l'ai et ne dévoile pas tout...)

par **Ben314** » 07 Déc 2009, 23:14

Bon, je fait un petit "up"
Trop façile ?
Trop dur ?
Pas interessant ?

P.S. j'ai cherché certains "mot clef" dans "enigme" pour voir si ça n'avait pas été déjà fait et j'ai vu du "semblable" mais pas complètement....

par **ffpower** » 08 Déc 2009, 09:51

Sans faire beaucoup d'efforts, je peux affirmer que le résultat appartient à {124,125}. (Au moins ca me fait un compte approchant ça^^)
Donc après, soit on trouve une config bizarre qui fait 125, soit nodgim a raison et faut trouver un invariant foireux. Pour ma part,j'opterais plutôt pour la seconde solution..

par **ffpower** » 08 Déc 2009, 10:06

Ok, c'était bien la 2nde solution :we:
Si on pave la boite, en ne sélectionnant qu'un "cube" sur 2 ( concretement, on on met un systeme de coordonnées pour représenter les 1000 cubes que contient la boite et on sélectionne les 500 cubes dont la somme des coordonnées est paire), chaque sucre occupera exactement 4 cubes, et 500 n'est pas un multiple de 4 :zen:

par **Ben314** » 08 Déc 2009, 10:18

EXACT.
Mais ce n'est pas tout à fait la réponse que j'attendais...
Comme j'ai la flemme de chercher un exemple "vicieux" je pose tout de go la question générale :
Trouver une C.N.S. pour que l'on puisse remplir une boite AxBxC avec des petits axbxc.

par **ffpower** » 08 Déc 2009, 10:23

Mais c'est qu'on fait le difficile en plus. Apres on va avoir droit à un sucrier hypercubique^^.Bon,bah je vais déja réfléchir à la version 2d

par **Ben314** » 08 Déc 2009, 10:29

En ce qui concerne le "hypercubique", la réponse est.... oui
(i.e. la preuve marche en toutes dimensions)

Tant qu'à faire, je voulais dire que ce casse tête m'avais occupé un bon moment il y a de nombreuse années et que la première solution que j'avais trouvé était de considérer les coordonnées des 125 centres de gravité des 125 sucres et... d'obtenir une contradiction.
Mais cela ne se généralise pas à tout axbxc...

par **Imod** » 08 Déc 2009, 15:24

Bonjour :we:

Y'a une réponse simple dans le cas général ??? Déjà en 2D ça ne semble pas évident :triste:

Imod

par **Ben314** » 08 Déc 2009, 17:41

Oui, il y a une réponse TRES simple dans le cas général (modulo un petit détail concernant le fait que pour que AxBxC puisse se remplir avec des axbxc, il faut que A,B,C soient combinaisons linéaires de a,b,c à coeffs dans N et que l'on ne sait pas résoudre "complètement" ce type de problème [c.f. nombres de Frobenius])

Pour donner un exemple du "petit détail", on peut remplir tout les rectangles Ax15 avec des 3x5 sauf, évidement, si A=1, 2, 4 ou 7

par **ffpower** » 08 Déc 2009, 18:47

pour les A*15,ok c'est facile en écrivant A=5x+3y. Bon,du coup, tu nous a donné une piste là^^

par **Ben314** » 08 Déc 2009, 19:23

Pour "la piste", sincèrement, pas du tout....
Dans les C.N.S., il y a celle là qui fait un peu "cheveux dans la soupe" par rapport aux autres qui sont évidentes à vérifier (ou à infirmer) même pour des nombres trés grand alors que celle là est connue pour être difficilement décidable pour de grands nombre...

par **nodgim** » 08 Déc 2009, 19:27

Ne faut il pas faire intervenir le demi périmètre du sucre ?

par **Ben314** » 08 Déc 2009, 19:30

non non (c'est plus simple....quand on connait la soluce)

par **ffpower** » 08 Déc 2009, 21:28

Bon ben déjà, si je ne me suis pas gourré, par des arguments de pavages (j y tiens^^), j'obtiens que si on peut remplir AxB par des axb, alors a divise A ou B et b divise A ou B. Et ca se généralise probablement.. et dans le cas ou par exemple a divise A et b divise B,c est trivial, donc on peut supposer que a et b divisent le meme coté, par exemple A ( bon ca,ca se généralise moins )

par **ffpower** » 08 Déc 2009, 21:34

Et quand a et b divisent A, il suffit de résoudre B=ax+by avec x,y entiers positifs pour avoir une solution ( je sais pas encore si c'est une CNS..)

par **Doraki** » 08 Déc 2009, 21:42

Oui c'en est une.
Si on a une solution alors en regardant une ligne on a une écriture de B en ax+by.
Si B=ax+by, on sait paver.

Donc on a fini le cas 2D ?

par **Ben314** » 08 Déc 2009, 21:53

Je suis pas super complètement sûr que vous ayez fait toute les déduction avant d'attaquer les AxBxC :
Avez vous bien réfléchi à ce que l'on peut remplir avec des 15x20 par exemple (en dim 2, la question est con-con mais ça aidera pour la dim 3,4,...)

Autre question, avez vous une preuve "carrée" ?

Sinon, les pavages, ca, c'est une bonne idée, mais, peut-être à un peu généraliser....

Bon courage....

P.S. le 15x20 c'est juste pour montrer que (a divise A et b divise B) ou bien (a et b divisent le même coté) c'est pas toujours totalement suffisant....

P.S.2. on va dire qu'en dim 2, c'est O.K. car on peut supposer a et b premier entre eux. Attention, en dim 3 on peut les supposer globalement premiers entre eux mais pas 2 à 2....

par **ffpower** » 08 Déc 2009, 22:46

Ah oui effectivement Doraki lol
Ben,quel est censé être le problème avec 15 et 20?
Sinon,je vais quand même écrire la preuve de mon "lemme de pavage" pour conclure le cas 2D. Supposons avoir une décomposition de AxB en axb. Je regarde le pavage suivant. A une case (x,y) j associe x+y modulo a, et on va dire qu a chaque classe,j associe une couleur ( histoire de mieux visualiser-en plus ca fera plaisir à Imod^^). Chaque rectangle axb contient exactement b cases de chaques couleur. En particulier, le grand rectangle AxB doit avoir autant de cases de chaque couleur. Et ceci doit aussi rester vrai si on réduit A et B modulo a. Si ni A ni B ne sont divisibles par a, on obtient donc un petit rectangle r1 x r2 avec r1,r2

La boite de sucre

la boite de sucre

Qui est en ligne