#012 1000

問題

 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個 の電球だと考えられる。

研究

コメント

タイトルとURLをコピーしました