hide or visible

問題の説明

古典的な整数問題です.どこかで見たことがある方もいるのではないでしょうか.問題文の補足をします.一番はじめにロッカーを開け閉めする生徒はすべてのロッカーを開けることになります(大変ですが).$2$番目の生徒は偶数の番号がつけられたロッカーをすべて閉めることになります.$3$番目の生徒は$3$の倍数のロッカーを開け閉めします.より正確にいえば,$6$の倍数のロッカーを開け,$6$で割って$3$余る番号のロッカーを閉めることになります.以下同様にして$200$番目の生徒が終わるまで操作が続きます.

ロッカーの数が$200$個もあるので,すべて実際にやってみるというのはとても大変です.どのように考えれば簡単に最終結果を知ることができるでしょうか.

時系列を無視する

問題文の状況の枠組みの中にとらわれないようにしましょう.つまり,この問題では,$200$人の生徒が順番にロッカーの開け閉めを行うという設定ですが,そのような時間的順序は問題の本質ではないのです.問題の本質はある番号のロッカーが結果的に開け閉めされる回数です.問われているのは最終的に開いているロッカーの個数ですから,奇数回開け閉めされるロッカーの数を求めればよいということになります.

整数問題に帰着

ロッカーが奇数回開け閉めされるとはつまりその番号の約数の個数が奇数個ということです.したがって約数の個数が奇数となるような数を探せばよいということになります.ここまで問題を消化してしまえばあとは普通の整数問題です.

補題:自然数$N$が平方数であることと,$N$の約数の個数が奇数となることは同値である.


補題の証明: $N$を素因数分解表示する.$N$は素数$p_1,...,p_k$と負でない整数$\alpha_1,...,\alpha_k$を用いて, $$N=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ と書ける.このとき,$N$の約数の個数は, $$(\alpha_1+1)(\alpha_2+1) \cdots (\alpha_k+1)$$ である.$N$が平方数なら$\alpha_1,...,\alpha_k$はすべて偶数なので,$N$の約数の個数は奇数となる.逆も当然成り立つ.

平方数の個数

上の補題から,最終的に開いているロッカーは番号が平方数のものということがわかります.$200$以下の平方数は$14$個あるので,答えは$14$個です.


問題の状況設定にとらわれないことがポイントです.