View source for Block-stacking problem

{{short description|Problem of stacking blocks so they extend as far as possible past their base}}
[[File:Block_stacking_problem.svg|thumb|300px|The first nine blocks in the solution to the single-wide block-stacking problem with the overhangs indicated]]
In [[statics]], the '''block-stacking problem''' (sometimes known as '''The Leaning Tower of Lire''' {{harv|Johnson|1955}}, also the '''book-stacking problem''', or a number of other similar terms) is a puzzle concerning the stacking of blocks at the edge of a table.

==Statement==

The block-stacking problem is the following puzzle:

<blockquote>Place <math>N</math> identical [[Stiffness|rigid]] [[rectangular]] blocks in a stable stack on a table edge in such a way as to maximize the overhang.
</blockquote>

{{harvtxt|Paterson|Peres|Thorup|Winkler|2007}} provide a long list of references on this problem going back to [[mechanics]] texts from the middle of the 19th century.

==Variants==
===Single-wide===
The single-wide problem involves having only one block at any given level.  In the ideal case of perfectly rectangular blocks, the solution to the single-wide problem is that the maximum overhang is given by <math display="inline">\sum_{i=1}^{N}\frac{1}{2i}</math> times the width of a block. This sum is one half of the corresponding [[harmonic series (mathematics)#Partial sums|partial sum of the harmonic series]]. Because the harmonic series diverges, the maximal overhang [[Limit (mathematics)|tends to]] [[infinity]] as <math>N</math> increases, meaning that it is possible to achieve any arbitrarily large overhang, with sufficient blocks.
{{Div flex row| justify-content=center}}
{| class="wikitable" style="white-space:nowrap;float:left;margin:0.5em;width:unset !important;"
! rowspan="2"|''N'' !! colspan="4"|Maximum overhang
|-
! colspan="2"|expressed as a fraction !! decimal !! relative size
|-
| style="text-align:right;"|1 || style="border-right:none;text-align:right;padding-right:0;"|1 || style="border-left:none;padding-left:0;"|/2 || {{bartable|0.5||20}}
|-
| style="text-align:right;"|2 || style="border-right:none;text-align:right;padding-right:0;"|3 || style="border-left:none;padding-left:0;"|/4 || {{bartable|0.75||20}}
|-
| style="text-align:right;"|3 || style="border-right:none;text-align:right;padding-right:0;"|11 || style="border-left:none;padding-left:0;"|/12 || ~{{bartable|0.91667||20}}
|-
| style="text-align:right;"|4 || style="border-right:none;text-align:right;padding-right:0;"|25 || style="border-left:none;padding-left:0;"|/24 || ~{{bartable|1.04167||20}}
|-
| style="text-align:right;"|5 || style="border-right:none;text-align:right;padding-right:0;"|137 || style="border-left:none;padding-left:0;"|/120 || ~{{bartable|1.14167||20}}
|-
| style="text-align:right;"|6 || style="border-right:none;text-align:right;padding-right:0;"|49 || style="border-left:none;padding-left:0;"|/40 || {{bartable|1.225||20}}
|-
| style="text-align:right;"|7 || style="border-right:none;text-align:right;padding-right:0;"|363 || style="border-left:none;padding-left:0;"|/280 || ~{{bartable|1.29643||20}}
|-
| style="text-align:right;"|8 || style="border-right:none;text-align:right;padding-right:0;"|761 || style="border-left:none;padding-left:0;"|/560 || ~{{bartable|1.35893||20}}
|-
| style="text-align:right;"|9 || style="border-right:none;text-align:right;padding-right:0;"|7&thinsp;129 || style="border-left:none;padding-left:0;"|/5&thinsp;040 || ~{{bartable|1.41448||20}}
|-
| style="text-align:right;"|10 || style="border-right:none;text-align:right;padding-right:0;"|7&thinsp;381 || style="border-left:none;padding-left:0;"|/5&thinsp;040 || ~{{bartable|1.46448||20}}
|}

{| class="wikitable" style="white-space:nowrap;float:left;margin:0.5em;width:unset !important;"
! rowspan="2"|''N'' !! colspan="4"|Maximum overhang
|-
! colspan="2"|expressed as a fraction !! decimal !! relative size
|-
| style="text-align:right;"|11 || style="border-right:none;text-align:right;padding-right:0;"|83&thinsp;711 || style="border-left:none;padding-left:0;"|/55&thinsp;440 || ~{{bartable|1.50994||20}}
|-
| style="text-align:right;"|12 || style="border-right:none;text-align:right;padding-right:0;"|86&thinsp;021 || style="border-left:none;padding-left:0;"|/55&thinsp;440 || ~{{bartable|1.55161||20}}
|-
| style="text-align:right;"|13 || style="border-right:none;text-align:right;padding-right:0;"|1&thinsp;145&thinsp;993 || style="border-left:none;padding-left:0;"|/720&thinsp;720 || ~{{bartable|1.59007||20}}
|-
| style="text-align:right;"|14 || style="border-right:none;text-align:right;padding-right:0;"|1&thinsp;171&thinsp;733 || style="border-left:none;padding-left:0;"|/720&thinsp;720 || ~{{bartable|1.62578||20}}
|-
| style="text-align:right;"|15 || style="border-right:none;text-align:right;padding-right:0;"|1&thinsp;195&thinsp;757 || style="border-left:none;padding-left:0;"|/720&thinsp;720 || ~{{bartable|1.65911||20}}
|-
| style="text-align:right;"|16 || style="border-right:none;text-align:right;padding-right:0;"|2&thinsp;436&thinsp;559 || style="border-left:none;padding-left:0;"|/1&thinsp;441&thinsp;440 || ~{{bartable|1.69036||20}}
|-
| style="text-align:right;"|17 || style="border-right:none;text-align:right;padding-right:0;"|42&thinsp;142&thinsp;223 || style="border-left:none;padding-left:0;"|/24&thinsp;504&thinsp;480 || ~{{bartable|1.71978||20}}
|-
| style="text-align:right;"|18 || style="border-right:none;text-align:right;padding-right:0;"|14&thinsp;274&thinsp;301 || style="border-left:none;padding-left:0;"|/8&thinsp;168&thinsp;160 || ~{{bartable|1.74755||20}}
|-
| style="text-align:right;"|19 || style="border-right:none;text-align:right;padding-right:0;"|275&thinsp;295&thinsp;799 || style="border-left:none;padding-left:0;"|/155&thinsp;195&thinsp;040 || ~{{bartable|1.77387||20}}
|-
| style="text-align:right;"|20 || style="border-right:none;text-align:right;padding-right:0;"|55&thinsp;835&thinsp;135 || style="border-left:none;padding-left:0;"|/31&thinsp;039&thinsp;008 || ~{{bartable|1.79887||20}}
|}
{| class="wikitable" style="white-space:nowrap;float:left;margin:0.5em; width:unset !important;"
! rowspan="2"|''N'' !! colspan="4"|Maximum overhang
|-
! colspan="2"|expressed as a fraction !! decimal !! relative size
|-
| style="text-align:right;"|21 || style="border-right:none;text-align:right;padding-right:0;"|18&thinsp;858&thinsp;053 || style="border-left:none;padding-left:0;"|/10&thinsp;346&thinsp;336 || ~{{bartable|1.82268||20}}
|-
| style="text-align:right;"|22 || style="border-right:none;text-align:right;padding-right:0;"|19&thinsp;093&thinsp;197 || style="border-left:none;padding-left:0;"|/10&thinsp;346&thinsp;336 || ~{{bartable|1.84541||20}}
|-
| style="text-align:right;"|23 || style="border-right:none;text-align:right;padding-right:0;"|444&thinsp;316&thinsp;699 || style="border-left:none;padding-left:0;"|/237&thinsp;965&thinsp;728 || ~{{bartable|1.86715||20}}
|-
| style="text-align:right;"|24 || style="border-right:none;text-align:right;padding-right:0;"|1&thinsp;347&thinsp;822&thinsp;955 || style="border-left:none;padding-left:0;"|/713&thinsp;897&thinsp;184 || ~{{bartable|1.88798||20}}
|-
| style="text-align:right;"|25 || style="border-right:none;text-align:right;padding-right:0;"|34&thinsp;052&thinsp;522&thinsp;467 || style="border-left:none;padding-left:0;"|/17&thinsp;847&thinsp;429&thinsp;600 || ~{{bartable|1.90798||20}}
|-
| style="text-align:right;"|26 || style="border-right:none;text-align:right;padding-right:0;"|34&thinsp;395&thinsp;742&thinsp;267 || style="border-left:none;padding-left:0;"|/17&thinsp;847&thinsp;429&thinsp;600 || ~{{bartable|1.92721||20}}
|-
| style="text-align:right;"|27 || style="border-right:none;text-align:right;padding-right:0;"|312&thinsp;536&thinsp;252&thinsp;003 || style="border-left:none;padding-left:0;"|/160&thinsp;626&thinsp;866&thinsp;400 || ~{{bartable|1.94573||20}}
|-
| style="text-align:right;"|28 || style="border-right:none;text-align:right;padding-right:0;"|315&thinsp;404&thinsp;588&thinsp;903 || style="border-left:none;padding-left:0;"|/160&thinsp;626&thinsp;866&thinsp;400 || ~{{bartable|1.96359||20}}
|-
| style="text-align:right;"|29 || style="border-right:none;text-align:right;padding-right:0;"|9&thinsp;227&thinsp;046&thinsp;511&thinsp;387 || style="border-left:none;padding-left:0;"|/4&thinsp;658&thinsp;179&thinsp;125&thinsp;600 || ~{{bartable|1.98083||20}}
|-
| style="text-align:right;"|30 || style="border-right:none;text-align:right;padding-right:0;"|9&thinsp;304&thinsp;682&thinsp;830&thinsp;147 || style="border-left:none;padding-left:0;"|/4&thinsp;658&thinsp;179&thinsp;125&thinsp;600 || ~{{bartable|1.99749||20}}
|}
{{clear}}
{{Div flex row end}}
<!-- Python script to generate n from 1 to 30:
import fractions
numerator = 0; denominator = 1
for i in range(1, 30 + 1):
 numerator = numerator * i * 2 + denominator; denominator *= i * 2; gcd = fractions.gcd(numerator, denominator); numerator /= gcd; denominator /= gcd
 decimal   = ('{}' if (i < 3 or i == 6) else '{:.5f}').format(float(numerator) / denominator); exact = '' if (i < 3 or i == 6) else '~'
 print('|-\n| style="text-align:right;"|{} || style="border-right:none;text-align:right;padding-right:0;"|{:,} || style="border-left:none;padding-left:0;"|/{:,} || {}{{{{bartable|{}||20}}}}'.
       format(i, numerator, denominator, exact, decimal).replace(',', '&thinsp;'))
-->

The number of blocks required to reach at least <math>N</math> block-lengths past the edge of the table is 4, 31, 227, 1674, 12367, 91380, ... {{OEIS|A014537}}.<ref>{{Cite OEIS|sequencenumber=A014537|name=Number of books required for n book-lengths of overhang in the harmonic book stacking problem.}}</ref>

===Multi-wide===
[[File:Block stacking problem compare 3.svg|thumb|250px|Comparison of the solutions to the single-wide (top) and multi-wide (bottom) block-stacking problem with three blocks]]
Multi-wide stacks using [[Counterweight|counterbalancing]] can give larger overhangs than a single width stack. Even for three blocks, stacking two counterbalanced blocks on top of another block can give an overhang of 1, while the overhang in the simple ideal case is at most {{sfrac|11|12}}. As {{harvtxt|Paterson|Peres|Thorup|Winkler|2007}} showed, asymptotically, the maximum overhang that can be achieved by multi-wide stacks is proportional to the cube root of the number of blocks, in contrast to the single-wide case in which the overhang is proportional to the logarithm of the number of blocks. However, it has been shown that in reality this is impossible and the number of blocks that we can move to the right, due to block stress, is not more than a specified number. For example, for a special brick with {{mvar|h}} = {{val|0.20|u=m}}, Young's modulus {{mvar|E}} = {{val|3000|u=MPa}} and density {{mvar|ρ}} = {{val|1.8|e=3|u=kg/m3}} and limiting compressive stress {{val|3|u=MPa}}, the approximate value of {{mvar|N}} will be 853 and the maximum tower height becomes {{val|170|u=m}}.<ref>{{Cite journal|url=http://iopscience.iop.org/article/10.1088/0031-9120/42/1/F05|doi = 10.1088/0031-9120/42/1/F05|title = Simplifying modelling can mislead students|year = 2007|last1 = Khoshbin-e-Khoshnazar|first1 = M. R.|journal = Physics Education|volume = 42|pages = 14–15| s2cid=250745206 }}</ref>

== Proof of solution of single-wide variant ==
The above formula for the maximum overhang of <math>n</math> blocks, each with length <math>l</math> and mass <math>m</math>, stacked one at a level, can be proven by [[Mathematical induction|induction]] by considering the [[torque]]s on the blocks about the edge of the table they overhang. The blocks can be modelled as point-masses located at the center of each block, assuming uniform mass-density. In the base case (<math>n=1</math>), the [[center of mass]] of the block lies above the table's edge, meaning an overhang of <math>l/2</math>. For <math>k</math> blocks, the center of mass of the <math>k</math>-block system must lie above the table's edge, and the center of mass of the <math>k-1</math> top blocks must lie above the edge of the first for static equilibrium.<ref>{{Cite web |last=Cazelais |first=Gilles |title=Block stacking problem |url=http://wrean.ca/cazelais/block_problem.pdf |archive-url=https://web.archive.org/web/20231204233816/http://wrean.ca/cazelais/block_problem.pdf |archive-date=December 4, 2023}}</ref> If the <math>k</math>th block overhangs the <math>(k-1)</math>th by <math>l/2</math> and the overhang of the first is <math>x</math>,<ref>{{Cite web |last=Joanna |date=2022-04-14 |title=The Infinite Block Stacking Problem or the Leaning Tower of Lire |url=https://www.mathscareers.org.uk/the-infinite-block-stacking-problem-or-the-leaning-tower-of-lire/ |access-date=2023-12-04 |website=Maths Careers |language=en-GB}}</ref>

<math>(k-1)mgx=(l/2-x)mg
\implies x=l/2k,</math>

where <math>g </math> denotes the [[gravitational field]]. If the <math>k-1</math> top blocks overhang their center of mass by <math>y</math>, then, by assuming the inductive hypothesis, the maximum overhang off the table is

<math>y+\frac{l}{2k}=\sum_{i=1}^k{l/2i} \implies y=\sum_{i=1}^{k-1}{l/2i} . </math>

For <math>k+1</math> blocks, <math>y</math> denotes how much the <math>k+1-1</math> top blocks overhang their center of mass <math>(y=\sum_{i=1}^k l/2i)</math>, and <math>x=\frac{l}{2(k+1)}</math>. Then, the maximum overhang would be:

<math>\frac{l}{2(k+1)}+\sum_{i=1}^k l/2i=\sum_{i=1}^{k+1} l/2i.</math> [[File:block_stacking_problem_skintled_4_diamond.svg|thumb|250px|Mike Paterson's method to increase the overhang of 16 blocks of unit width and breadth ''b'' to 2{{sqrt|1 + ''b''&thinsp;²}} by offsetting the blocks perpendicular to their lengths in a diamond formation&thinsp;<ref>M Paterson et al., [http://maa.org/sites/default/files/pdf/upload_library/22/Robbins/Patterson2.pdf ''Maximum Overhang''], The Mathematical Association of America, November 2009</ref>]]

==Robustness==
{{harvtxt|Hall|2005}} discusses this problem, shows that it is [[wikt:robust|robust]] to nonidealizations such as rounded block corners and finite precision of block placing, and introduces several variants including nonzero [[friction]] forces between adjacent blocks.

==References==
<references />
*{{Cite journal
 | first = J. F. | last = Hall
 | title = Fun with stacking blocks
 | journal = American Journal of Physics
 | volume = 73 | issue = 12 | year = 2005 | pages = 1107–1116
 | doi = 10.1119/1.2074007
 | bibcode = 2005AmJPh..73.1107H}}.
*{{cite journal
 | last = Johnson | first = Paul B.
 | bibcode = 1955AmJPh..23..240J
 | date = April 1955
 | doi = 10.1119/1.1933957
 | issue = 4
 | journal = American Journal of Physics
 | pages = 240
 | title = Leaning Tower of Lire
 | volume = 23}}
*{{cite arXiv
 | last1 = Paterson | first1 = Mike | author1-link = Mike Paterson
 | last2 = Peres | first2 = Yuval | author2-link = Yuval Peres
 | last3 = Thorup | first3 = Mikkel | author3-link = Mikkel Thorup
 | last4 = Winkler | first4 = Peter | author4-link = Peter Winkler
 | last5 = Zwick | first5 = Uri | author5-link = Uri Zwick
 | title = Maximum overhang
 | year = 2007
 | eprint = 0707.0093
 | class = math.HO 
 }}

== External links ==
* {{MathWorld | urlname=BookStackingProblem | title=Book Stacking Problem}}
* {{cite web | url=https://www.pbs.org/video/building-an-infinite-bridge-xwh5bz/ |title=Building an Infinite Bridge |website=[[PBS Digital Studios|PBS Infinite Series]] |date=2017-05-04 |access-date=2018-09-03}}

[[Category:Statics]]
[[Category:Mathematical problems]]