SLP2018 Cうめ

SLP 2018 C3

概要

n+1個のマスが横一列に並んでいる。左端にn個の石が置かれている。
以下の操作を繰り返し行う。

石がk個あるマスから一つ石を選び、1~kマス右に移動する。

この時n個の石を全て右端に配置するためには[n/1]+[n/2]…+[n/n]([r]でr以上の最小の整数を表す)回以上の操作を必要とすることを示せ。

証明

（一連の操作で、ゴール（右端にたどり着く）順に石に1~nの番号をつける。→石iは石i-1までがゴールしているため条件より最大でもn-iしか動けない。したがって[n/(n-i)]回の操作がこの石に対して必要→ただしゴール前での順序に依存してしまうため、この部分を考慮する必要がある。→初めから番号をつけておき、操作を決める。）
予め石に1~n番号をつける。各操作で、小さい番号の石を選ぶことにする。
石kを動かしたということは選んだマスにはk以上の番号が書かれた石しかないため、最大でもn-kしか動けない。よって石kがゴールするためには[n/(n-k)]回操作が必要となる。これを足し合わせればよい。

感想

C2より簡単な気がした。
解説もほぼ同じ。確かに大きい番号選んだ方がみやすいな。
式から距離kずつ移動する石があれば良さそうなのは気づくのでそうなるようにストーリーづけ（上手な番号づけ、言い換え）をする感じ。
発展として等号が成立するnを全て求めよというのがあったので考える。

→わからん