Voir la source de Problème d'empilage de blocs

[[File:Block_stacking_problem.svg|thumb|upright=1.5|
Les huit premiers blocs de la solution du problème d'empilement de blocs de même largeur, avec surplombs indiqués.]]
En [[statique (mécanique)|statique]] (et en [[mathématiques récréatives]]), le '''problème d'empilage de blocs''' (aussi le  '''problème d'empilage de livres''', ou d'autres dénominations similaires) est une devinette concernant l'empilage possible de blocs sur le bord d'une table. Au lieu d'empilements de blocs, on rencontre aussi des étalements de cartes à jeux<ref>{{MathWorld| nom_url=BookStackingProblem | titre=Book Stacking Problem}}.</ref>.

== Description ==

Le ''problème d'empilement de blocs'' est le puzzle suivant :

<blockquote>Comment poser <math>N</math> blocs  [[Rectangle|rectangulaires]] et [[Raideur (mécanique)|rigides]] sur le bord d'une table de manière à maximiser le surplomb.
</blockquote>

== Historique ==
[[Fichier:A pile of coins demonstrating the divergence of a harmonic series.jpg|thumb|Un empilement de pièces de monnaie ; la pièce du haut est entièrement hors de la région au-dessus de la pièce la plus basse.]]
Le problème d'empilement de blocs a une longue histoire, à la fois en [[mécanique (science)|mécanique]]  et comme problème de [[Mathématiques récréatives|récréation mathématique]]. Dans leurs articles {{sfn|Paterson|Zwick|2009}}{{,}}{{sfn|Paterson|Peres |Winkler|Zwick|2009}},
Paterson et ses coauteurs fournissent une longue liste de références sur ce problème qui est traité dans des écrits de [[mécanique (science)|mécanique]] remontant jusqu'au milieu du {{s-|XIX}}. Il fait aussi partie sous une autre forme des récréations mathématiques étudiées par [[Martin Gardner]]{{sfn|Gardner|1971}}{{,}}<ref>{{Youtube|chaîne = El Jj|titre = Deux (deux ?) minutes pour l'escargot de Gardner|id = L1vDkUziBpw|langue = fr}}.</ref> par exemple.

== Variantes ==
=== Empilage simple ===
Dans le modèle à empilage simple (''single-wide problem''),  il y a un seul bloc à chaque niveau.  Quand les blocs sont tous identiques et rectangulaires, le surplomb maximal <math> d_N </math> pour <math>N</math> blocs est{{sfn|Paterson|Peres |Winkler|Zwick|2009}} 

: <math>d_N=\frac12\sum_{i=1}^{N}\frac{1}{i}=\frac12H_N</math>. 
C'est la moitié de la somme partielle de la [[série harmonique]]. Les premiers termes sont :
:{| class="wikitable"  style="align:center;font-size:95%;line-height:1.0;text-align:center;white-space:nowrap;"
|- 
|''N'' || 1 || 2 || 3 ||4||5||6||7||8||9
|-
| <math>d_N</math>||1/2||3/4||11/12||25/24||137/120||49/40||363/280||761/560||7129/5040
|}
Ces nombres forment les suites {{OEIS2C|A001008}} et  {{OEIS2C|A002805}} de l'[[OEIS]].
Comme la série harmonique diverge, le surplomb maximum  [[Limite (mathématiques)|tend vers]] l'[[infini]] avec  <math>N</math>, ce qui signifie que l'on peut réaliser des surplombs arbitrairement grands à condition d'empiler un nombre suffisant de blocs. Asymptotiquement, le surplomb maximal est
:<math>\frac12\ln\, N</math>.

=== Empilage multiple ===
[[File:Block stacking problem compare 3.svg|thumb|upright=1.2|Comparaison de l’empilement simple (en haut) et de l'empilement multiple (en bas) avec 3 blocs.]]
[[File:Empilage.png|thumb|Empilage surplombant maximal avec 20 blocs identiques.]]
Lorsque l'on utilise plusieurs blocs à chaque niveau le [[contrepoids]] intervient pour permettre de réaliser des surplombs plus grands. Déjà avec trois blocs, deux blocs au dessus du premier niveau peuvent se contrebalancer et donnent un surplomb de 1, alors que dans le cas simple, le surplomb est au plus 11/12. Paterson et Zwick, puis Paterson, Peres, Winkler et Zwick{{sfn|Paterson|Zwick|2009}}{{,}}{{sfn|Paterson|Peres |Winkler|Zwick|2009}} ont montré le surplomb maximal que l'on peut atteindre est asymptotiquement
:<math>c\sqrt[3]N</math>
ce qui contraste avec le cas simple où le surplomb est proportionnel au logarithme du nombre de blocs. Pour des petits nombres de blocs, il existe des solutions plus optimales{{sfn|Paterson|Peres |Winkler|Zwick|2009}}.

== Robustesse ==
{{harvsp|Hall|2005}} étudie le problème de l'empilement en tenant compte de contraintes physiques, telles la robustesse des matériaux, les coins éventuellement arrondis, la précision du placement des blocs, et introduit certaines variantes comme des forces de [[frottement]] non nulles entre des blocs adjacents.

== Notes et références ==
{{Traduction/Référence|en|block-stacking problem|789206302|type=note}}
{{Références}}

== Bibliographie ==
* {{article
 | prénom = John F. | nom = Hall
 | titre = Fun with stacking blocks
 | journal = American Journal of Physics
 | volume = 73 | numéro = 12 | année = 2005 | pages = 1107-1116
 | doi = 10.1119/1.2074007
 }}.
* {{article
 |auteur1=[[Mike Paterson]]|auteur2= [[Uri Zwick]]
 |titre=Overhang|journal=Amer. Math. Monthly 
 |volume=116|numéro=1|année=2009|pages=19-44
 |math reviews= 2011b:68182|arxiv=0710.2357
 |lire en ligne = https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Paterson.pdf}} — Une première version est parue dans {{article 
 |titre= Overhang
 |journal= Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06)
 |année = 2006
 |éditeur= Society for Industrial and Applied Mathematics
 |lieu= Philadelphie|pages=  231-240}}.
* {{article
 |auteur1=Mike Paterson
 |auteur2=[[Yuval Peres]] 
 |auteur3=[[Peter Winkler]]
 |auteur4= Uri Zwick
 |titre=Maximum overhang
 |journal=Amer. Math. Monthly 
 |volume=116|numéro=9|année=2009
 |pages=763-787|math reviews= 2011b:68183
 |arxiv=0707.0093
 |lire en ligne = https://www.maa.org/sites/default/files/pdf/upload_library/22/Robbins/Patterson2.pdf}}.
*{{Ouvrage
|lang=en
|auteur1=[[Martin Gardner]]
|titre=Martin Gardner’s Sixth Book of Mathematical Games from "Scientific American"
|éditeur=W.H. Freeman & Co Ltd
|année=janvier 1971
|numéro d'édition=6
|pages totales=262
|isbn=978-0-7167-0944-2
}}.

== Lien externe ==
* {{MathWorld| nom_url=BookStackingProblem | titre=Book Stacking Problem}}

{{Portail|mathématiques}}

[[Catégorie:Statique]]
[[Catégorie:Problème mathématique]]