★ 第 26 回問題 ★


ある村では次のような占いによって村長を選出する.
まず, s 個の小石を器に入れる. 村民 n 人が輪に並び, そのうち一人に器が渡される. 村民は器が手元に来たとき この村民の行動 1 回を 1 ステップと呼ぶ. ある村民が s 個全ての小石を持ったとき,その村民が村長となり占いが終了する.

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

応募は締め切りました.

第 26 回問題解説・正解者発表へ/ 問題一覧へ /トップページへ ●2554
出題: 2009 年 9 月 10 日 (木) 19 時 00 分 00 秒
締切: 2009 年 10 月 10 日 (土) 23 時 30 分 00 秒
解説・正解者発表: 2009 年 11 月 7 日 (土) 19 時 30 分 00 秒
担当者: 片岡 俊基