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 ?

Salut

Si j’ai bien compris le problème

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.

j'ai du mal à voir, un ensemble pire



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 .

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 )

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.

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.

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

Vasimolo

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

Vasimolo

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.

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.

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

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.

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 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 :

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.