Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 20-09-2015 17:56:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

gâtrau 106

Bonjour à tous smile

Ce n’est sans doute pas le gâteau du siècle mais je l’ai cuisiné tout seul avec une seule  main et deux ou trois petits neurones que je trouve un poil poussifs en ce moment lol

Mon pâtissier a confectionné 25 gaufrettes rectangulaires dont les côtés sont des entiers ne dépassant pas 16 ( centimètres ) .

Est-il assuré de pouvoir empiler 4 de ces gaufrettes sans qu’aucune d’entre elles ne déborde sur celles du dessous ?

http://www.prise2tete.fr/upload/Vasimolo-gateau106(2d).png

Le but du jeu n’est pas de faire un montage acrobatique genre château de cartes mais bien de poser bêtement les gaufrettes à plat , les unes sur les autres tongue

Une vue 3D pour les amateurs :

http://www.prise2tete.fr/upload/Vasimolo-gateau106(3d).png

Bon courage et amusez-vous bien smile

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 21-09-2015 07:45:54

looozer
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 697
Lieu: Belgique

gâteai 106

Bonjour à tous,

Imaginons le plus mauvais scénario pour le pâtissier.

Pour que deux gaufrettes rectangulaires de dimensions entières ne puissent être superposées sans débordement, il faut que l'une soit supérieure en longueur et que l'autre soit supérieure à la en largeur.

Avec des entiers entre 1 et 16, on peut faire un maximum de telles paires en prenant : 16-1; 15-2; 14-3; 13-4; 12;5; 11-6; 10-7 et 9-8

Avec 3 fois ce jeu de gaufrettes (soit 24 gaufrettes), seules les pièces identiques pourront être empilées on pourra alors atteindre au maximum un empilement de 3 pièces.

Une 25ème gaufrette aura, soit une forme identique à un trio déjà existant, soit des dimensions lui permettant de supporter ou d'être superposée à un trio de pièces identiques.

Donc je dirais que c'est Ok pour le pâtissier.

 #3 - 21-09-2015 08:36:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

gâteai 106

Je suppose que tu parles de 25 gaufrettes toutes de tailles différentes ? Car affleurer n'est pas déborder. Et sans doute tu parles de 4 gaufrettes prises au hasard, auquel cas on pourrait empiler les 25 ?

 #4 - 21-09-2015 13:23:47

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

gâteai 106

@Looozer : C'est sûrement le bon angle d'attaque mais il faudrait justifier pourquoi la position considérée est la "pire" smile

@Nodgim : le problème n'est pas dans ce sens . Les 25 gaufrettes sont données au hasard parmi toutes les gaufrettes possibles ( on pourrait avoir 25 fois la même ) . Ensuite il faut en choisir 4 dans le lot et les empiler comme demandé . Peut-on envisager un lot de gaufrettes où ce choix est impossible ?

Vasimolo

 #5 - 21-09-2015 13:48:18

nobodydy
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1677

Gâeau 106

Salut

Si j’ai bien compris le problème sad

Imaginons 25 gaufrettes identiques, je peux en prendre 4 et les empiler sans qu’elles débordent.

Si maintenant je prends 8 séries de 3 gaufrettes
De 16x1, 15x2, 14x3 etc…. 8x9 soit 24 gaufrettes

Dans cette configuration, je ne peux pas empiler 4 gaufrettes sans débordement

Mais il reste une gaufrette, quelque soit sa dimension, je pourrais la poser soit dessus, soit dessous.

Donc il y aura toujours une possibilité d'empiler 4 gaufrettes.

 #6 - 21-09-2015 14:17:26

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Gâtteau 106

Oui Nobodydy , tu es parti sur la même idée que Looozer , mais qui te dit que cette configuration est la pire possible ?

Vasimolo

 #7 - 21-09-2015 15:02:45

nobodydy
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1677

Gâtea 106

j'ai du mal à voir, un ensemble pire sad

http://www.prise2tete.fr/upload/nobodydy-vasimolo-gaufrettes.png

il y a 136 tailles différentes possibles de 16x16 .......1x1

Sur un 16x16, toutes les tailles de 16x16...à..16x1, peuvent aller dessus
Sur un 16x15, blablabla idem de  16x15 à  16x1 etc.....

seules les gaufrettes 16x1 , 15x2 etc... 8x9 sont totalement incompatibles entre elles

maintenant

je suis incapable de le démontrer (dans le sens où tu l'entends)
Si il y a pire dit le moi clairement, et je m'amuserai à chercher
sinon, je m'arrêterai là pour ma démonstration du siècle big_smile.

donc je pense qu'il sera toujours possible de les empiler s'il y a 25 gaufrettes.
(mais j'espère me tromper. Ce serait plus drôle wink )

 #8 - 21-09-2015 15:48:50

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Gâteu 106

Pour qu'on ne puisse pas empiler 4 gâteaux, il faudrait déjà qu'avec 24 on ne puisse pas.

On ne peut éviter la condition de 4 superposables que d'une seule façon avec 24 gâteaux. Il faut faire 3 gâteaux de chacune des 8 formes :
16x1, 15x2, 14x3, ..., 9x8.

En effet, on ne peut faire que 8 gâteaux non superposables deux à deux.
Leurs dimensions sont 16x1, 15x2, 14x3, ..., 9x8.
Toute autre forme est soit incluse dans l'un de ces gâteaux ou inclut l'un d'eux.

Le 25ème empiète sur - ou est contenu dans - l'un des 24 existants.

Conclusion : on peut toujours trouver 4 gâteaux empilables sans débordement.

 #9 - 21-09-2015 16:26:51

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3220
Lieu: Luxembourg

Gâteau 06

Est ce que tu veux dire qu'on tire 4 gaufrettes au hasard sur les 25 disponibles ?
Il suffirait sinon de choisir les "bonnes" gaufrettes et il n'y aurait plus d'énigme.

 #10 - 21-09-2015 16:42:53

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

gâreau 106

@Franky : les 4 gaufrettes sont choisies mais pas le lot de 25 .

@Nobodydy & Halloduda : Avez-vous montré que le lot de 24 gaufrettes que vous proposez est le seul avec lequel on ne peut pas ériger une pyramide de 4 étages ? Si c'est le cas , le problème est bien sûr résolu smile

Vasimolo

 #11 - 21-09-2015 19:37:42

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Gâtaeu 106

J'ai envie de faire simple :

Chaque gaufrette a une largeur et une longueur et donc 2 dimensions.

Si une même dimension apparaît plus de 3 fois, cela fera plus de 3 gaufrettes superposables.
24 gaufrettes, c'est 24 longueurs et 24 largeurs, soit 48 dimensions.
Au delà, une dimension apparaîtra 4 fois.

Après, on peut supposer qu'une gaufrette est carrée, voire 2 ou même 3 (pas plus car elles seraient empilables) . Admettons...

Mais ça ne change pas le problème, car une gaufrette de dimension n x n au milieu de rectangles stricts est tout à fait équivalente à une gaufrette n x (n+1) à part le cas trivial de 16 x 16. Donc si le problème a une solution avec une gaufrette carrée, il en aurait une avec des rectangles purs.

 #12 - 21-09-2015 21:02:19

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1494
Lieu: Coutiches

Gâteu 106

Bon, j'imagine que comme tout le monde je suppose que la pire situation est d'avoir 3 gaufrettes de chacune des dimensions suivantes :
1-16
2-15
3-14
4-13
5-12
6-11
7-10
8-9
Et que donc tout autre 25ème permettra de construire la tour.

Mais je n'ai pas non plus la démonstration...

 #13 - 21-09-2015 21:28:15

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

gâteai 106

@Golgot : oui , tu rejoins les autres smile
@Gwen : tu peux clarifier le cas des gaufrettes carrées ?

Vasimolo

 #14 - 21-09-2015 21:56:04

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Gâteau 16

Si on peut empiler une gaufrette carrée dans une gaufrette rectangulaire, on peut la remplacer par une gaufrette rectangulaire de dimension juste supérieure en largeur ou en longueur.

Donc, si le problème est soluble avec des gaufrettes carrées, cela revient à dire qu'il est soluble avec des gaufrettes rectangulaires uniquement.

Or , je prouve juste avant qu'une solution avec des rectangles stricts est impossible.

Si le carré est de 16 x 16 , on s'en fiche, ou au pire on le remplace par 15 x 16

 #15 - 21-09-2015 22:12:59

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

GGâteau 106

Possible avec certaines gaufrettes carrées => possible avec gaufrettes uniquement rectangulaires : d'accord .

Mais sauf erreur , il me semble que le raisonnement que tu utilises fonctionne dans l'autre sens .

J'ai pu raté quelque chose smile

Vasimolo

 #16 - 22-09-2015 07:46:56

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Gâteau 06

Possible avec certaines gaufrettes carrées => possible avec gaufrettes uniquement rectangulaires

Est équivalent à

"Impossible avec des gaufrettes rectangulaires => impossible avec des gaufrettes carrées"

Je crois que c'est une contaposée, non ?

Cette relation logique permet d'évacuer le cas assez embarrassant des carrés.

On en revient donc au cas assez simple des rectangles :
Une 49e dimension deviendra la quatrième occurrence d'une des mesures et donc 4 gaufrettes seront empilables au moins.

 #17 - 22-09-2015 08:12:42

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Gâteau 10

On peut fabriquer 8 modèles non superposables en 3 exemplaires chacun de demi périmètre 17, soit de 16*1 à 9*8. ça fait 24 gaufrettes avec lesquelles il est impossible de faire un gâteau de 4 gaufrettes superposées. Mais s'il faut une 25ème gaufrette, on ne peut pas l'éviter.

 #18 - 22-09-2015 08:23:41

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Gâteeau 106

@Nobodydy & Halloduda : Avez-vous montré que le lot de 24 gaufrettes que vous proposez est le seul avec lequel on ne peut pas ériger une pyramide de 4 étages ? Si c'est le cas , le problème est bien sûr résolu smile

Vasimolo

On peut faire 136 différentes tailles de gaufrettes rectangulaires.
1≤x≤y≤16.
L'étude exhaustive est vite faite, ou me trompé-je ?.

 #19 - 22-09-2015 13:17:15

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 382

gâtezu 106

Notons ( Li, li ) les dimensions de la gaufrette i

Classons les 25 gaufrettes par longueur décroissante et en départage par largeur croissante.

Raisonnons par l'absurde en considérant que ces 25 gaufrettes ne "fonctionnent" pas, et remplaçons les 3 premières gaufrettes par  (16,1)

On voit clairement que cette configuration ne "fonctionne"  pas non plus (Il ne peut pas y avoir une 4eme gaufrette de longueur 16 ni de largeur 1 sinon ça "fonctionnerait" et dans le cas contraire, les 3 gaufrettes initiales ne peuvent pas "servir" vu que les autres ont une taille (<16,>1) et ne sont pas compatibles

On recommence le process de substitution en remplaçant les 3 prochains par (15,2) puis (14,3 )... jusqu'à (9,8) en remarquant les même notions d'incompatibilité entre les différents paquets.

Il reste une gaufrette dans cette nouvelle configuration que nous avons montré être plus défavorable que l'initiale.

Cette dernière gaufrette a une longueur >=9 ou un largeur <8 et on peut donc l'ajouter a un paquet de 3 gaufrettes identiques dont il aura la même longueur ou même largeur et qui formera un quartet gagnant.

La solution modifiée fonctionne donc ce qui contredit l'hypothèse initiale.

De manière générale avec des gaufrettes de taille maximum M et en voulant empiler P gaufrettes
si M pair  il faut au minimum M/2 * P + 1 gaufrettes
Si M impair  il en faut  (M+1) /2 * P + 1 gaufrettes (la "transformée" acceptant un carré)

Edit 1 : il manquait le 2 apres le / dans "Si M impair  il en faut  (M+1) /2 * P + 1 gaufrettes (la "transformée" acceptant un carré)"

Nota bene : Ce raisonnement est en effet probablement artificiellement alourdi et il n'est peut être pas indispensable de passer par un raisonnement par l’absurde dont je ne sus pas certain que cela en soit un.. J'ai essayé de simplifier mais je me heurte au problème des carrés qui semblent poser des difficultés aux posteurs... C'est d'ailleurs le fait, quand la longueur max est impaire, qui fait apparaître le carré final et crée le +1 dans la formule.

 #20 - 22-09-2015 17:41:17

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Gâteau 1066

@Nodgim : tu rejoins les autres : affirmer que dans la pire des situations on a trouvé une solution et donc dans tous les autres cas ne veut pas vraiment dire grand-chose . Il faut définir en quoi cette situation est la pire smile

@Holloduda : 25 gaufrettes choisies parmi 136 modèles différents , bien sûr on peut épuiser tous les cas mais c'est assez lourd et ça manque sérieusement d'élégance .

@Gwen : je dois faire un blocage , je n'arrive pas à voir comment tu évacues les carrés smile

@Portugal : pour moi c'est juste mais s'il fallait rédiger complètement la solution , ...
   On peut peut-être simplifier tout ça smile

Vasimolo

 #21 - 22-09-2015 19:32:42

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Gâteau 1006

Bon, je me lance (de là à dire que je vais me ramasser ! lol)

Le pire des cas, pour moi, ce serait d'avoir des gaufrettes de dimensions 1*16, 2*15, 3*14... 7*10 et 8*9... Aucune de ces 8 gaufrettes ne peut se superposer. Je n'ai pas trouvé de démonstration immédiate, mais quelques traits de crayon semblent bien montrer qu'on ne peut gérer à la fois longueur et largeur.

Mais toute autre gaufrette sera superposable (ou sous-posable si j'ose dire) avec au moins l'une d'entre elles. Une gaufrette 5*14 pourra aller sous la 3*14 ou sous la 5*12. Il n'en faut pas + de 2, sinon on a notre pyramide de 4 gaufrettes.
Une gaufrette de 6*13 n'est plus insérable sous la 5*12. De même, il n'en faut pas plus de 2...

On pourra donc, au pire, avoir 8 pyramides de 3 gaufrettes, + 1 gaufrette qu'on pourra également insérer dans une des ces pyramides. Etant entendu que des gaufrettes de mêmes dimensions sont superposables.


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #22 - 22-09-2015 19:41:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

gâtrau 106

Ben oui Fix , tu es comme tout le monde , tu as mis le doigt sur la position critique . Après il faut justifier et là c'est fatiguant smile

Vasimolo

 #23 - 22-09-2015 23:30:17

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

fâteau 106

Considérons la gaufrette l*L, avec l+1<L, entiers > 0 et < 17.

(l+1)*(L-1) = l*L + L-l -1 > l*L
Donc la gaufrette l*L ne peut être posée qu'au-dessus d'une gaufrette (l+1)*(L-1).

Ne "suffirait"-il pas de prouver que ?
L^2 > (l+1-a)^2 + (L-1-b)^2, pour tout a et b réels positifs tels que a^2 + b^2 = 1.

La quantité de droite étant le carré de la plus longue gaufrette de côté 1 pouvant être superposée à la gaufrette (l+1)*(L-1), et la quantité de gauche étant le carré de la longueur de notre gaufrette qu'on voudrait bien placer dessus...


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #24 - 23-09-2015 18:05:26

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 382

Gââteau 106

Juste une remarque. Contrairement a ce que beaucoup disent 16-1 ...9-8 n'est pas LA seule solution a 24 gaufres. Remplacer 9-8 par 99 ou 88 donne le méme résultat (contrairement au cas ou la longeur maxi est impaire car là, on est forcé de mettre un carré si on veut "optimiser" la structure et cette dois il n'y a pas de choix.)

 #25 - 23-09-2015 19:02:36

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

gâtezu 106

lollollol
Je comprends rarement tes problèmes du premier coup... et il faut toujours que je m'explique 2 fois.



Etape 1 : 25 rectangles stricts donnent 50 dimensions différentes 2 à 2 dans les rectangles. Ce qui veut dire que parmi les 16 dimensions possible, il y en a au moins 1 qui revient plus de 3 fois. Donc, on pourra toujours empiler 4 formes vu qu'elles ont la même longueur ou la même largeur

Etape 2 : Je vais varier un peu pour plus de clarté.

Bon, un dessin :
http://www.prise2tete.fr/upload/gwen27-g106dessin.png
Hypothèse :
Admettons qu'un jeu de 25 formes (carrés possibles) ne permette pas de superposer 4 des formes...
Imaginons que , à part les pièces de largeur 1, on diminue la largeur de chaque pièce de 1 unité.

Cela ne change strictement rien aux possibilités de superposition quelles que soient les pièces choisies.
Ah, oui, il reste le cas du carré 1 x 1 , transformons le en 2 x 1.

On a donc construit un lot de 25 rectangles stricts qui n'autorise aucune superposition de 4 pièces.

Donc, si un jeu de 25 rectangles dont des carrés ne permet pas de superposer 4 formes, alors je peux trouver un jeu de 25 rectangles stricts qui ne le permette pas non plus....

Etape 3 : Vu la conclusion du 1, l'hypothèse du 2 est impossible.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 10 hommage par Vasimolo
28-06-2010 Enigmes Mathématiques
P2T
Gâteau 110 par Vasimolo
01-11-2015 Enigmes Mathématiques
P2T
Gâteau 69 par Vasimolo
02-02-2014 Enigmes Mathématiques
P2T
Gâteau 103 par Vasimolo
02-08-2015 Enigmes Mathématiques
P2T
Gâteau 118 par Vasimolo
11-01-2016 Enigmes Mathématiques
P2T
Gâteau 43 par Vasimolo
05-11-2011 Enigmes Mathématiques
P2T
Gâteau 146 par Vasimolo
12-10-2017 Enigmes Mathématiques
P2T
Gâteau 35 par Vasimolo
12-02-2011 Enigmes Mathématiques
P2T
Gâteau 71 par Vasimolo
15-02-2014 Enigmes Mathématiques
P2T
Gâteau 34 par Vasimolo
24-09-2010 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete