Nombre maximal de pièces dans un coffre

shinitchi · April 2021

Bonjour à tous,
je m'excuse dans un premier temps parce que je ne savais pas dans quel forum mettre ce problème...

Je joins le problème en pdf où il s'agit de mettre un maximum de pièces d'or (de dimensions données) à l'intérieur d'un coffre (de dimensions données). J'obtiens un nombre par tests mais suis incapable de démontrer qu'il s'agit bien du nombre maximum. Je n'ai absolument aucune idée de comment faire pour traiter ce genre de problème de façon théorique afin de le généraliser à n'importe quelles dimensions de pièce et de coffre.

Est-ce que le nombre de pièces que j'obtiens est bien le max ? Si oui, comment faire pour le démontrer ?
En vous remerciant par avance.

Fin de partie · April 2021

Les problèmes d'empilement sont souvent des problèmes difficiles.

Pour ton problème: Ce qui est certain est qu'on ne peut pas entasser plus de $1096$ pièces* (nombre obtenu en divisant le quotient du volume du coffre par le volume d'une pièce et en prenant l'entier qui est inférieur au résultat trouvé).

*: si je n'ai pas fait d'erreur de calcul.

Ludwig · April 2021

En les empilant comme dans tes trois derniers étages on obtient déjà $6 \times 3 \times \frac{9}{0,2} = 810$ pièces.
Il me semble qu'on peut ensuite placer $3\times 3 =9 $ pièces dans chacun des six gros espaces restants.
Ce qui fait $864$ pièces en tout.

Domi · April 2021

Bonjour shinitchi
Il s'agît en effet d'un problème difficile (d'où sort-il ?). On peut essayer de trouver le meilleur remplissage en disques de l'une des faces du coffre (ce n'est pas une partie de plaisir), puis remplir avec des cylindres de pièces comme tu l'as fait. Ensuite il faut combler les espaces entre les cylindres avec des pièces parallèles à l'axe des cylindres et choisir la meilleure configuration, là encore c'est une horreur. On peut aussi mélanger des cylindres de pièces dans les trois directions et pourquoi pas glisser des murs de pièces entre cylindres ailleurs que sur les bords ?

En bref , amuse-toi bien :-D
Domi

shinitchi · April 2021

@Ludwig,
dans les 3 "gros" espaces du haut, il y a bien 3 pièces qui peuvent y loger $\times$ 3 étages. Par contre dans les espaces du bas, il n'y a que $2$ pièces qui peuvent y loger $\times$ 3 étages.
Donc en effet, on peut faire mieux que $849$ avec $810 + 3\times 3 \times 3 + 2\times 3 \times 3 = 855$.
Merci à toi !

@Domi problème que je me suis posé et que j'ai "créé", il y a deux ans, certainement inspiré d'un autre mais dont je ne me souviens plus.

Je pensais naïvement qu'il y avait une théorie bien ficelée sur ce genre de problème avec des formules établies.
Si quelqu'un trouve mieux que Ludwig, je suis preneur !

Ludwig · April 2021

En bas à droite loge $3$ pièces et non $2$, ce qui fait $858$ pièces au total.

Fin de partie · April 2021

On peut baisser la borne maximum du nombre de pièces possible si on croit que, à chaque fois qu'on ajoute une pièce on ne rajoute pas seulement le volume occupé par la pièce mais tout le volume du parallélépipède rectangle dans lequel s'inscrit cette pièce ce qui fait qu'on obtient une borne maximum égale à $860$

shinitchi · April 2021

@Ludwig : sauf erreur de ma part, il n'y en a que deux qui logent dans le coin en bas à droite. J'ai fait un dessin sur geogebra pour le vérifier.

@fin de partie : oui, mais là tout de suite, je ne le crois pas. D'autant qu'avec le dessin où les pièces sont placées en quinconce chacune d'elle ne prend pas un espace égale à celui du plus petit parallélépipède rectangle qui la contient. Ah moins que j'y vois mal ce qui n'est pas à exclure.

Ludwig · April 2021

Je l'ai fait aussi aussi shinitchi, et je trouve $AB \approx 0,625$.
Quoi qu'il en soit je me demande si ce nombre maximal soit, en pratique, vraiment calculable. Car comment examiner toutes les configurations possibles? C'est très compliqué! De plus, en admettant qu'on ait obtenu la liste des configurations optimales, celles-ci me semblent éminemment dépendantes des dimensions du coffre : tu changes un chouia une dimension et hop la configuration optimale n'est plus la même. 120124

Ludwig · April 2021

On peut même en mettre quatre au lieu de deux, en haut, première ligne des piles, contre le bord du coffre. Total $864$.

shinitchi · April 2021

@Ludwig ; au temps pour moi, tu as raison. Ça passe tout juste en effet. Allons y pour 858, qui dit mieux ?

shinitchi · April 2021

@Ludwig, désolé mais je ne vois pas pour les 4 au lieu de 2. Parles-tu du coin en haut à gauche de ton dessin géogébra ?

shinitchi · April 2021

@Ludwig : ah oui, absolument, c'est bien vu une fois encore ! Va pour 864...

shinitchi · April 2021

en poursuivant le travail de Ludwig, j'ai pu caser une pièce supplémentaire sur $3$ étages soit $867$ pièces au total (voir pdf joint). Il y a probablement mieux au vu des améliorations successives depuis $849$...Si quelqu'un voit, je suis toujours preneur. 120136

Ludwig · April 2021

Dans toutes ces constructions les pièces debout sont placées sur la tranche, bien verticales. Or il est possible je crois de les incliner légèrement, par exemple pour celles du bas, contre la paroi du coffre. De sorte que leur sommet soit plus bas, et donc éventuellement en mettre plus au dessus. Ici je pense que c'est quand même trop serré, mais cela donne une idée de ce qu'on peut faire en plus.

shinitchi · April 2021

Dans cette configuration, ça semble en effet trop serré mais c'est une piste que je n'ai pas du tout exploré.

Intuitivement et sans réfléchir, j'aurai tendance à penser que si on penche les pièces pour gagner un étage d'une épaisseur de 0,2cm, c'est que le rangement ainsi fait sous cet étage n'était pas optimal. J'entends par là que le fait de pencher les pièces pour gagner un étage de 0,2 cm, t'aurais fait perdre plus de pièces que tu n'en gagneras sur cet étage "gagné".

Maintenant, mon intuition est loin d'être une référence alors à creuser...

Nombre maximal de pièces dans un coffre

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 16