��� 膃� 26 �����馹� ���

ある村では次のような占いによって村長を選出する.
まず, s 個の小石を器に入れる. 村民 n 人が輪に並び, そのうち一人に器が渡される. 村民は器が手元に来たとき

• 器に小石が 1 個以上あれば小石を 1 つとり器を右隣の人に渡し,
• 器に小石がなければ持っている小石を全て器に入れ器を右隣の人に渡す.

この村民の行動 1 回を 1 ステップと呼ぶ. ある村民が s 個全ての小石を持ったとき，その村民が村長となり占いが終了する.

(1) 村長は有限ステップで選出されることを示せ.
(2) s が n＋1 で割り切れないとき, 村長が選出されるまでのステップ数を n＋1 で割った余りが 1 であることを示せ.

綽�������膩������������障�����.