Packing Boxes
Bonjour à tous
J'adore fouiller dans les vieux problèmes d'olympiades en français ou en english ( même si je ne comprends pas toujours tout ) .
Voilà deux versions d'un problème du tournoi des villes de 2005 :
Version melon :
In a rectangular box are a number of rectangular blocks, not necessary identical to one another. Each block has one of its dimensions reduced. Is it always possible to pack these blocks in a smaller rectangular box, with the sides of the blocks parallel to the sides of the box ?
Version béret :
Un jeu est constitué de parallélépipèdes rectangles identiques. On peut les ranger dans une boîte qui est aussi un parallélépipède rectangle. A cause d'une erreur de fabrication, un exemplaire du jeu a été fabriqué avec des pièces toutes identiques ayant un côté strictement plus court que la pièce originale. Est-il possible de ranger toutes ces pièces dans une nouvelle boîte dont deux côtés sont identiques à ceux de la première boîte et le dernier strictement plus petit ?
Les pièces sont rangées de telle manière que chacun de leurs côtés soit parallèle à un côté de la boîte.
On a clairement affaire à deux problèmes différents .
Domi
J'adore fouiller dans les vieux problèmes d'olympiades en français ou en english ( même si je ne comprends pas toujours tout ) .
Voilà deux versions d'un problème du tournoi des villes de 2005 :
Version melon :
In a rectangular box are a number of rectangular blocks, not necessary identical to one another. Each block has one of its dimensions reduced. Is it always possible to pack these blocks in a smaller rectangular box, with the sides of the blocks parallel to the sides of the box ?
Version béret :
Un jeu est constitué de parallélépipèdes rectangles identiques. On peut les ranger dans une boîte qui est aussi un parallélépipède rectangle. A cause d'une erreur de fabrication, un exemplaire du jeu a été fabriqué avec des pièces toutes identiques ayant un côté strictement plus court que la pièce originale. Est-il possible de ranger toutes ces pièces dans une nouvelle boîte dont deux côtés sont identiques à ceux de la première boîte et le dernier strictement plus petit ?
Les pièces sont rangées de telle manière que chacun de leurs côtés soit parallèle à un côté de la boîte.
On a clairement affaire à deux problèmes différents .
Domi
Réponses
-
Bonjour @Dominique & co,
La version béret était-elle censée donner une traduction de l'énoncé anglais ?
Pour le peu que je comprenne l'anglais, le problème initial est plus intéressant .
Mais voilà :
Si dans une boîte 10 x 12 x 14 sont rangés 8 pavés 5 x 6 x 7
Imaginons que nous ayons à présent
3 pavés 4,9 x 6 x 7
3 pavés 5 x 5,9 x 7
Et 2 pavés 5 x 6 x 6,9
Je ne pense pas qu'il existe une plus petite boîte parallélépipédique qui pourrait les contenir tous.
Ai-Je bien compris le problème ? -
Bonjour Jacquot,
Il est clair que ta solution convient pour le problème anglais . Le problème français n'est pas le même ( il est moins intéressant ? ) , c'est curieux ( peut-être existe-t-il des versions junior-senior à difficultés variables ) .
Domi -
Bonjour Domi,
La version béret me semble triviale.
À moins que je ne l'aie pas bien lue.::o
Pour la version anglaise, je me demandais s'il n'y avait pas un seuil pour le nombre de pièces à partir duquel la boîte existerait forcément.
Pour des rangements cubiques, ça pourrait être $a^2\leqslant \dfrac {a^3}3$
Voudrais-tu donner une traduction de l'inglish énoncé ?
Tu sais ma faiblesse dans ce languige. :-D
Amicalement. jacquot -
Mon anglais n'est pas de grande classe : On range des pavés ( pas forcément de même taille ) dans un parallélépipède rectangle . On réduit une dimension de chacun des pavés , est-on toujours assuré de pouvoir ranger les nouvelles pièces dans une boîte plus petite ?
Domi
PS : le problème Français est si simple ? -
Pour le problème français, il y a peut-être moyen de fabriquer un contre-exemple avec des pavés tous identiques mais pas tous rangés dans le même sens.
-
C'est sans doute l'idée mais tu as un exemple concret ?
Domi -
Non, je n'ai pas (encore ?) d'exemple.;-)
-
Bon, Domi, veux-tu vérifier cette solution au problème français:
5 pavés 2x3x6 sont rangés dans une boîte 4x6x8
Il n'y a pas de place pour un sixième pavé et je crois qu'il n'y a guère qu'un rangement possible voir ci-dessous.
Si je réduis les dimensions des 5 pavés à 2x 2,9 x6, je ne peux réduire aucune dimension de la boîte sans empêcher la possibilité du rangement.
Je n'ai pas trouvé de solution avec une boîte initiale telle que son volume égale la somme des volumes des pavés.
Je ne trouve pas ces problèmes bien passionnants, mais peut-être suis-je passé à côté de leur intérêt :-S
Amicalement. jacquot -
Bonsoir Jacquot
Qu'est-ce qui fait qu'un problème est intéressant ou pas ? Apparemment celui-ci n'intéresse pas grand monde mais il m'intrigue et je fais part de ma curiosité . Les deux problèmes sont clairement différents et je ne suis pas sûr que la version française soit plus simple .
Il me semble qu'en basculant le pavé isolé derrière pour le poser dessus on obtient un pavé 4 X 6 X 7,8 .
En tout cas merci pour la participation :-D
Domi -
::o Tu as raison, pour le basculement du pavé. Il est taquin, ce problème.
-
Sauf erreur , il me semble qu'en dimension 2 , la réduction des longueurs ou des largeurs des rectangles réduit forcément la dimension de la boîte . La troisième dimension offre bien plus de possibilités et je pense qu'il y a des tas de contre-exemples , même si comme toi , je n'arrive pas à mettre doigt sur l'un d'entre eux ,
La version béret ne méritait peut-être pas d'être balayée d'un simple revers de main :-D
Domi -
Tu as raison en tous points, Domi.
Mais je ne suis pas très motivé pour cette recherche... -
Bonjour Domi,
Je mets un lien vers la discussion ouverte par soland.
Les deux questions sont peut-être connexes.
Cube de Denis Hoffmann -
Bonjour à tous .
En fouillant sur le site je suis retombé sur ce vieux problème . Jacquot avait participé chaleureusement mais sans enthousiasme ( merci à lui (tu)) . Une idée pour la version béret ?
Domi -
Edit
La version béret me parait vrai au moins lorsque le parrallélipipède est plein de pavés identiques,
parce que dans ce cas si on peut réarranger tous les pavés dans le même paralléllipipède en ayant leur face qui a diminué dans le même coté (qu'on diminue) c'est gagné.
Pour réarranger les pavé $x\times y\times z$ de cette façon on montre une certaine relation entre $x,y,z$ que je pense trouvable
par exemple quand il existe $a,b,c$ entiers tel que $ax=by=cz$...
Mon avis.
Cordialement. -
Je reviens toujours ( maladivement ) sur mes vieux problèmes :-D
Pour la version béret la réponse est assurément : non !
En fait la solution est assez bête lorsqu'on l'a trouvée .
Domi -
Bonsoir, mais est ce non aussi si initialement le parallélipipède est plein de pavés? (béret).
-
Oui , j'étais aussi parti sur un remplissage imparfait . On peut trouver une boîte parfaitement remplie par les briques telle qu'en réduisant une dimension ( dans une proportion raisonnable ) , la boîte gardera la même taille .
Domi -
D'accord une contrainte si les pavés ont au moins deux côté égaux ?
-
On peut ajouter des contraintes à un problème qui n'est déjà pas facile au départ , pour le moment je vais apprécier ma solution :-D
Domi -
100%
-
Une solution : on peut réduire légèrement la longueur 4 mais on va rester dans la même boîte .
Domi -
Bonjour. Merci, voulez-vous que je mette la conjecture -ultimate- parce qu'elle m'a pris en émotions:-D (dés une semaine)
-
Je ne vois pas trop ce que tu veux dire , j'ai toujours grand plaisir à partager les problèmes qui m'intéressent et après chacun en fait ce qu'il veut :-D
Domi -
On arrive à la conjecture trés jolie:
Des parallélépipèdes n-dimentionnelles identiques à $n-s$ côtés égaux sont rangé dans une boîte qui est
aussi un parallélépipède. A cause d'une erreur
de fabrication, un exemplaire du jeu a été fabriqué avec
des pièces toutes identiques ayant $1$ côté strictement
plus court que la pièce originale. Est-il possible de ranger
toutes ces pièces dans une nouvelle boîte dont $n-s$
côtés sont identiques à ceux de la première boîte et le reste
strictement plus petit. (Sans question car je vois que oui).
Même synthaxe de Domi.
Pour ne pas trop imaginer moi j'aime bien le cas où $s=1$..
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 26
+19 Invités