代表選考合宿 2019
問題 7

$n$ 個の石に番号 $1,2,\dots,n$ をつけ，操作に以下のルールを追加しても操作の合計回数は変わらない．

• 石をあるマスから動かすとき，動かす石はそのマスにある番号が最も大きい石とする．

このとき，番号 $k$ の石を動かすとき元のマスには石が $k$ 個以下存在しているので，移動距離は $k$ 以下である．よって番号 $k$ の石をマス $0$ からマス $n$ に動かすためには番号 $k$ の石を動かす操作を $\lceil n/k\rceil$ 回以上する必要がある．以上より全ての石をマス $n$ に移動するためには操作を

$$\left\lceil \dfrac{n}{1}\right\rceil+\left\lceil \dfrac{n}{2}\right\rceil+\cdots+\left\lceil \dfrac{n}{n}\right\rceil$$

回以上行う必要がある．