第１１７問の解答
１．問題 ［規則性］
|
円のまわりに、１〜２００までの番号の書かれたボールを右周りに小さい順に並べていきます。 このボールを１のボールから右周りに１つおきに取っていきます。円を一周してしまった後もボールがなくなるまでこの作業を続けます。 このとき、最後に取ることになるボールは何番のボールでしょうか。 |
２．解答例１（H.Takaiさん、Hiroさん、kuri他）
まず、１回目に、奇数を全て取ることになり、偶数が残ります。
次に、２回目は、４の倍数が残り、それ以外を取ることになります。
また、３回目は、８の倍数が残り、それ以外を取ることになります。
そして、４回目は、１６の倍数が残り、それ以外を取ることになります。ところが、４回目で残ったボールは、２５個で奇数になりますので、５回目は２個目の３２から取っていくことになるので、３２の倍数を除き、それ以外が残ることとなります。
以下、図のごとく取っていき、最後に１４４が残ります。以上
２．解答例２（ＴＯＲＡさん、kuri他）
１個から、１６個までの場合を考えてみます。
すると、次のような規則性があることが分かります。
すなわち、２のべき乗単位で周期的に、２，４，６，８・・・・と２づつ増えていくようです。
従って、２００個の場合、これより小さな２のべき乗は１２８ですから、最後に残るのは、（２００−１２８）×２＝１４４となることが分かります。
以上
３．解答例３（ありさのお父さん、kuri他）
解答例２で予想した規則性を式にしてみましょう。
ボールの個数がｎ個のとき、最後に残る番号をf(n)とします。まず、f(1)＝１、f(2)＝２は明らかですね。
ちなみに、ｎが２のべき乗に等しいとき、ｍ＝ｎ／２だから、f(ｎ)＝ｎとなり、それ以外のときは、f(ｎ)≦ｎ−２となります。
次に、ｎ≧３のとき、ｎより小さい２のべき乗で最大のものをｍとすると、f(ｎ)＝（ｎ−ｍ）×２・・・式Ａ となります。さて、これをｎに（２≦ｎ）関して数学的帰納法により、証明してみます。
（はじめに）
ｎ＝３のとき、解答例２より、f(3)＝２だから、式Ａは成り立ちます。（帰納法の仮定） ｎ＝ｋ（３≦ｋ）のときに、式Ａが成り立つと仮定します。
（ｎ＝ｋ＋１のとき）
最初の１個（１の番号のボール）を取ります。残りは、ｋ個です。
次は、残ったボールの２番目（３の番号のボール）を取ることになるので、残る２の番号のボールを最後尾に回すことにします。
もし、ｋが２のべき乗だとすると、仮定より、f(ｋ)＝ｋですので、最後尾の２の番号のボールが最後に残ることとなります。従って、f(ｎ)＝２となります。
また、ｎ＝ｋ＋１より小さくて最大の２のべき乗はｋということになるので、ｍ＝ｋ、従って、（ｎ−ｍ）×２＝２となり、式Ａは成立します。
もし、ｋが２のべき乗ではないものとすると、f(ｋ)≦ｋ−２なので、最後に残るボールは、最後の２個ではあり得ません。ボールは３からならんでいますので、結局f(ｋ＋１)＝f(ｋ)＋２＝（ｋ−ｍ）×２＝（ｋ＋１−ｍ）×２となります。
また、ｋが２のべき乗ではないので、ｎ＝ｋ＋１より小さくて最大の２のべき乗は、ｎ＝ｋのときのｍに等しくなります。
よって、先ほどのf(ｋ＋１)＝（ｋ＋１−ｍ）×２は、ｎ＝ｋ＋１のときも式Ａが成り立つことを意味します。
以上から、数学的帰納法により、３≦ｎの全てのｎに関して式Ａが成立することとなります。
以上
