ブロック積み上げ問題

ブロック積み上げ問題は、以下のようなパズルが基になっている:

互いに全く同一とみなせる剛体直方体のブロックが ${\displaystyle N}$ 個ある。これを机の上に安定的に積み上げていく時、最も机の端からはみ出すような積み上げではどの程度のはみ出しを実現できるか?

Paterson et al. (2007) では、19世紀半ばの力学の教科書にまで遡る、この問題に関する膨大な参考文献リストを提示している。

各ブロックのすぐ上には1個だけしかブロックを置けないとする。さらに、各ブロックが完璧な直方体でその質量分布が一様であり、その上重力加速度がどこでも一様とする(現実的には高さとともに重力加速度は弱くなる上、十分大きなはみ出しのもとでは重力源の曲率の効果を無視できなくなる)と、 ${\displaystyle N}$ ブロックまででの机からのはみ出しは最大でブロックの幅の ${\textstyle \sum _{i=1}^{N}{\frac {1}{2i}}}$ 倍であることが示される。これは調和級数の部分和であり、調和級数が${\displaystyle N\to \infty }$ で無限大へと発散することから、${\displaystyle N\to \infty }$ の極限では机からのはみ出しもいくらでも大きくなる。つまり、十分なブロックの数があれば、どんな長さに対してもそれよりはみ出しを大きくすることができる。

オンライン整数列大辞典の数列 A014537によれば、ブロック整数個分の幅よりもはみ出しが大きくなるために必要となるブロックの数の最低値は、小さい方から 4, 31, 227, 1674, 12367, 91380, ... である。^[2]

1個のブロックの上に複数個のブロックを置いてもいい場合、いくつかのブロックをカウンターウエイトとして使うことで、より大きなはみ出しを少ないブロック数で作ることができる。例えば、ブロック3個を積み上げる場合、それぞれのブロックを縦にだけ積み上げる場合に実現可能な最大のはみ出しはブロックの幅の 11/12 倍であるが、ブロック1個の上に2個のブロックを積み上げる方法では、はみ出しとしてブロック1個分の幅を実現できる。Paterson et al. (2007) によれば、1個のブロックのすぐ上に積み上げられるブロックの数が1個に限られる場合では、${\displaystyle N}$ 個のブロックを使って実現できる最大のはみ出しは ${\displaystyle \log N}$ に比例して大きくなっていくが、1個のブロックの上に複数のブロックを乗せられる場合の最大のはみ出しは(${\displaystyle \log N}$ より高速な) ${\displaystyle N^{1/3}}$ に比例して大きくなっていく。

なお、ブロックの応力の影響で、現実的にははみ出しには上限値が存在する^[3]。

Summarize Timeline Top Qs Fact Check

幅が ${\displaystyle l}$、質量が ${\displaystyle m}$ で、質量密度が一様であるようなブロック ${\displaystyle n}$ 個を縦に積み上げていき、そのタワーが達成可能なはみ出しの最大値を求める。以下では、積み重ねたブロックを、上から1個目、2個目、...と数えることとする。また、${\displaystyle k}$ 番目のブロックがすぐ下にあるブロック(または机)からどれだけ外にはみ出しているかを ${\displaystyle x_{k}}$ で表す。最終的な目標は、「タワーがタワーとして存在できるような${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$の組み合わせの中での、${\displaystyle x_{1}+x_{2}+\cdots +x_{n}}$の最大値を求める」ことである。

質量密度が一定の仮定のもとでは、ブロックを重心にある質点に置き換えることができる。 ${\displaystyle k+1}$ 番目のブロックの端を基準とすれば、${\displaystyle (k+1-i)}$ 番目のブロックの重心は ${\displaystyle \sum _{j=1}^{i}x_{k+1-j}-l/2}$ だけはみ出た位置にある ${\displaystyle (i=1,2,\ldots ,k)}$。これら全てが ${\displaystyle k+1}$ 番目の端まわりのトルクに寄与する。上から ${\displaystyle k}$ 番目までの積み重ねたブロックが崩れないためには、${\displaystyle k+1}$ 番目のブロックの端まわりの正味のトルクが0以下である必要がある:

${\displaystyle {\begin{aligned}\sum _{i=1}^{k}\left(\sum _{j=1}^{i}x_{k+1-j}-{\frac {l}{2}}\right)mg&\leq 0\\\therefore \sum _{j=1}^{k}jx_{j}&\leq {\frac {k}{2}}l\end{aligned}}}$

ここで ${\displaystyle g}$ を重力定数とした。この条件がそれぞれの ${\displaystyle k}$ について成立する範囲であれば、ブロックの積み重ねはどの階層からでも崩壊することはない。よって、最大のはみ出しを求める問題は、次のような線形計画法の問題に帰着される:

${\displaystyle {\begin{aligned}&\mathrm {Maximize} &x_{1}+\cdots +x_{n}\\&\mathrm {s.t.} &x_{1}\leq {\frac {l}{2}}\\&&x_{1}+2x_{2}\leq l\\&&\vdots \\&&x_{1}+2x_{2}+\cdots +nx_{n}\leq {\frac {n}{2}}l\end{aligned}}}$

これを解くと、 ${\displaystyle x_{1}=l/2,x_{2}=l/4,\ldots ,x_{n}=l/(2n)}$が得られ、結果的にはみ出しの最大値は

${\displaystyle \sum _{k=1}^{n}{\frac {l}{2k}}}$

となる。