 pc ( No.4 ) |
- 日時： 2009/07/23 12:44
- 名前： nn)/
- (1) m = 6 で，以下のようにうまく選べます．
● １３４４
● ２４５５
○ ３５⑥
○ ４⑥
○ ５１１⑥
○ ⑥
● １２２
● ２３３
m = 20 でも ○ だけを選べます．
● １９７５２９６２８４９４９
○ ２０８６３⑳
○ ３１９７４１７３９５０５⑳
○ ４２⑳
○ ５３１８５２８４⑳
● ６４２９６３９５１６１６
● ７５３０７４０６２７２７
● ８６４１８５１７３８３８
他に，m = 30, 36, 50, 55, 61, 71, 85, 91, ... でも可能です．
この問題をとり上げていた，ある本では m = 30 になっていました．
(2) 選ばれると一人ずつ抜けていきますから，形式的には，選ばれた人の一人
前を順に選ぶことに相当する m = 0 が答えになっています．
そして，最初は 2n 人でできていた輪が，最後の一人を選ぶ直前には n+1 人の輪
になっていることに着目しますと，m = LCM(2n, 2n-1, ..., n+1) またはその正整
数倍とすれば，何人の輪であろうと，周囲を回転して実質 m = 0 の位置に来るよ
うになります．なお，LCM は最小公倍数のことです．
あとは，最後の ○ の次の ● の先頭から数え始めれば良い訳です．なお，最初の
数え始め場所をうまく選べば， m = LCM(2n-1, 2n-2, ..., n+1) と m を少し小さ
くすることができます．
また，各回で数え始めの人を選ぶことに相当する形式解 m = 1 を使って，
m = LCM(2n, 2n-1, ..., n+1) + 1, m = LCM(2n-1, 2n-2, ..., n+1) + 1
とするのも正しい答です．
(おまけ) (2) の答えは，無数にある m の存在を示すため，そのうちのひとつを
具体的に挙げたもので，もちろん，(n=2 以外) 最小値ではありません．
どのような値が m の最小値になるかは分かりませんでしたので，簡単なプログラ
ムを書いて n = 2, 3, ..., 10 に対する m の値を求めました．以下に，小さい順に
6 個ずつ示しておきます．
２： 3, 4, 6, 7, 9, 10 （全て 3 の倍数または 3 で割って 1 余る数です）
３： 5, 9, 12, 16, 20, 21 （以降は，これらに 20 の倍数を足した数です）
４： 6, 20, 30, 36, 50, 55 （LCM(7, 6, 5) +1= 211 までに ４! = 24 個）
５： 30, 72, 120, 127, 162, 169
６： 322, 351, 378, 441, 497, 504
７： 200, 649, 712, 729, 792, 1000
８： 1080, 1441, 2341, 2629, 2772, 3070
９： 1740, 4861, 4930, 10320, 15181, 15301
10： 2772, 2927, 20593, 25454, 41328, 42769
どうやら，0, 1 を含めた M(n) = LCM(2n-1, 2n-2, ..., n+1) 未満の m の総数が，
n 人を選び出す順番の総数（順列の数） n! に等しく，M(n) 以上の m はその n! 個
のどれかを使って m = m' + k M(n) (0 ≦ m' < M(n), k は正整数） と書けるよう
で，これくらいは背理法を用いて証明できそう（n! より多くても少なくても矛盾が
生じることを示す）です．
しかし，１より大きい最小の m がどのような n の関数として書けるか (つまりどう
いう選出順に対応するか) は，ヒマでヒマで仕方ないとき (そんな時が来るのでしょ
うか？) のためにとっておくことにします．やってみたら，案外簡単かも知れません
が，どうでしょうか ……
|
|
FAQ
RSS