問題
1～1000の数字が振られている1000個の電球がある。すべてOFFの状態から始めて、1回目の操作で1の倍数の電球のスイッチのON/OFFを切り替え、2回目の操作では2の倍数の電球のON/OFFを切り替える。
このように、n回目の操作でnの倍数の電球のON/OFFを切り替える操作を、1000回目までおこなったとき、最後にONの状態の電球の数は何個か。
イズミの解答への道
実験してみると法則性は分かるので、答えは分かるだろう。理論的に説明するには高校の知識が必要である。
解答
実験で求める
10個の場合で実験してみよう。
- ×××××××××× （スタート時）
- ○○○○○○○○○○ （1回目）
- ○×○×○×○×○× （2回目）
- ○×××○○○××× （3回目）
- ○××○○○○○×× （4回目）
- ○××○×○○○×○ （5回目）
- ○××○××○○×○ （6回目）
- ○××○×××○×○ （7回目）
- ○××○×××××○ （8回目）
- ○××○××××○○ （9回目）
- ○××○××××○× （10回目）
となり、3つの電球がONの状態で終了する。さてここで、この残った電球の番号は 1 , 4 , 9 となっており、「最後に残るのは n2 （平方数）の番号の電球」ではないかと予想される。
この予想から計算すると、1000以下の最大の平方数は 312 = 961 , 322 =1024 より、1 , 4 , 9 , … , 961 ( = 312 ) の 31個 の電球だと考えられる。
論証
さて、以下では上の予想を証明しよう。
まずは例をあげよう。6番目のスイッチは 1 回目、 2 回目、 3 回目、 6 回目の操作でON/OFFが切り替わり、偶数回のため結局OFFとなる。この 1 , 2 , 3 , 6 という数字は、6の倍数である。
つまり、 n 番目の電球は、 n の約数の個数の分だけスイッチが切り替わる。偶数個であればOFFに、奇数個であればONになる。
ある数 n の約数の個数 m は、 n の因数分解
n = a1k1 × a2k2 × … × aiki
において、
m = ( k1 + 1 ) ( k2 + 1 ) … ( ki + 1 )
である。この値が奇数になるのは、 ki がすべて偶数であるときであり、それはすなわち n が n = a2 で表される数（平方数）であるときである。（以上より、上記の予想が正しいことが示された。）
1000以下の最大の平方数は 312 = 961 , 322 =1024 より、1 , 4 , 9 , … , 961 ( = 312 ) の 31個 の電球だと考えられる。
コメント