第117問の解答


1.問題 [規則性

 円のまわりに、1〜200までの番号の書かれたボールを右周りに小さい順に並べていきます。

 このボールをのボールから右周りに1つおきに取っていきます。円を一周してしまった後もボールがなくなるまでこの作業を続けます。

 このとき、最後に取ることになるボール何番のボールでしょうか。


2.解答例1(H.Takaiさん、Hiroさん、kuri他)

参考図

 まず、1回目に、奇数を全て取ることになり、偶数が残ります。
 次に、2回目は、4の倍数が残り、それ以外を取ることになります。
 また、3回目は、8の倍数が残り、それ以外を取ることになります。
 そして、4回目は、16の倍数が残り、それ以外を取ることになります。

 ところが、4回目で残ったボールは、25個で奇数になりますので、5回目は2個目の32から取っていくことになるので、32の倍数を除き、それ以外が残ることとなります。
 以下、図のごとく取っていき、最後に144が残ります。

以上



2.解答例2(TORAさん、kuri他)

参考図2

1個から、16個までの場合を考えてみます。

 すると、次のような規則性があることが分かります。

 すなわち、2のべき乗単位で周期的に、2,4,6,8・・・・と2づつ増えていくようです。

 従って、200個の場合、これより小さな2のべき乗128ですから、最後に残るのは、(200−128)×2=144となることが分かります。

以上


3.解答例3(ありさのお父さん、kuri他)

 解答例2で予想した規則性を式にしてみましょう。
 ボールの個数がn個のとき、最後に残る番号をf(n)とします。

 まず、f(1)f(2)は明らかですね。
 次に、n≧3のとき、より小さい2のべき乗で最大のものをとすると、f(n)=(n−m)×2・・・式A となります。

 ちなみに、2のべき乗に等しいとき、/2だから、f(n)=nとなり、それ以外のときは、f(n)≦n−2となります。

 さて、これをに(2≦)関して数学的帰納法により、証明してみます。

(はじめに)
 n=3のとき、解答例2より、f(3)=2だから、式Aは成り立ちます。

(帰納法の仮定)  (3≦)のときに、式Aが成り立つと仮定します。

(n=k+1のとき)

参考図2

 最初の1個(の番号のボール)を取ります。残りは、k個です。

 次は、残ったボールの2番目(の番号のボール)を取ることになるので、残るの番号のボールを最後尾に回すことにします。

 もし、kが2のべき乗だとすると、仮定より、f(k)=kですので、最後尾のの番号のボールが最後に残ることとなります。従って、f(n)=2となります。

 また、k+1より小さくて最大の2のべき乗はkということになるので、、従って、()×2=2となり、式Aは成立します。

 もし、kが2のべき乗ではないものとすると、f(k)≦k−2なので、最後に残るボールは、最後の2個ではあり得ません。

 ボールはからならんでいますので、結局f(k+1)f(k)+2=()×2=(k+1)×2となります。

 また、kが2のべき乗ではないので、n=k+1より小さくて最大の2のべき乗は、n=kのときのに等しくなります。

 よって、先ほどのf(k+1)=(k+1)×2は、n=k+1のときも式Aが成り立つことを意味します。

 以上から、数学的帰納法により、3≦の全てのに関して式Aが成立することとなります。

以上