20個の電球と点灯のタイミング【0042】
問題文を表示▼
1~20番の番号付きの20個の電球があり ます。時刻を1秒目から始め、各電球は 時刻の秒数が自分の番号の倍数のときは 点灯し、そうでないときには消灯します。 最初に11個点灯するのは何秒後ですか。 2回目に11個点灯するのは何秒後ですか。
方針はいくつかありますが、面倒くさい方針を選ぶと特に2回目を探す時に大変かもしれません。
ちなみに最初の作問時は電球は10個で7,8,9個付くタイミングを聞いていました。でも似た問題が既出でありそうなオーラを感じたのでもうちょっと難易度を上げました。
困った時だけヒントを見ましょう
ヒント1を表示▼
ある秒数において点灯する電球は、「その秒数の20以下の約数」です。つまり、20以下の約数がちょうど11個ある整数を探す問題と言い換えられます。
しかし、この考え方で小さい順から探すのは大変そうです。どの11個を残せば良いのかはっきりしません。
ヒント2を表示▼
「最初に20個点灯する時刻」、「最初に19個点灯する時刻」から考えてみましょう。
ヒント3を表示▼
「最初に20個点灯する時刻」は1~20の最小公倍数です。これを とします。
「最初に19個点灯する時刻」は1~20から19を除いたものの最小公倍数です。この値は です。
ヒント4を表示▼
「最初に16個点灯する時刻」は1~20から19,17,13,11を除いたものの最小公倍数です。何か除くたびに最小公倍数ががくっと減りますね。
ここから先、後5個消灯させますが、ここからパズル要素が増えていきます。
例えば2と7が点灯しているのに14を消灯することはできません。
なるべく一度に消灯させる電球は少なく、しかも最小公倍数は小さくなるように数を選んでいきます。
