20個の電球と点灯のタイミング【0042】 解答・解説

1〜20の最小公倍数 $M = 2 \times 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19$ を考えます。 (一応算数のサイトなので$2^4$ という表記はしていません。)

この時刻では20個すべての電球が点灯しています。

ここから9個の電球を消すために、Mをできるだけ大きな数で割っていきます。

割る数を最大化すれば、残る時間が最小化されるためです。

Mをできるだけ大きな数で割るためには、電灯をなるべく残しつつ割る数を大きくします。

つまり 19, 17, 13, 11 の素数の電球は消灯させます。

これによって、残りの電灯は16個です。

ベースとなる時間は $L = 2 \times 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 = 5040$ となります。

次に、電球を個別に選ぶのではなく、「5040のどの素因数を削ると、どの電球が連動して消えるか」を調べます。

• $\div 7$ $\implies$ 【2個消える】(7, 14)
• $\div 5$ $\implies$ 【4個消える】(5, 10, 15, 20)
• $\div 3$ $\implies$ 【2個消える】(9, 18)
  • $\div 9$ $\implies$ 【6個消える】(3, 6, 9, 12, 15, 18)
• $\div 2$ $\implies$ 【1個消える】(16)
  • $\div 4$ $\implies$ 【2個消える】(16, 8)
  • $\div 8$ $\implies$ 【5個消える】(16, 8, 4, 12, 20)
  • $\div 16$ $\implies$ 【10個消える】(16, 8, 4, 12, 20, 2, 6, 10, 14, 18)

上の一覧からあと5個消える組み合わせで最大の割る数を作ります。

5が奇数なので、$\div 8$ の単発で5個を消さない限り、$\div 2$ で1個消すことが必須です。この時 $\div 4$、 $\div 8$などの素因数が2だけの数 (2の累乗) は考えなくてよくなります。

そのうえでさらに4個を電灯を消したいです。割る数を最大にするには

• $\div 7$ で2個消す
• $\div 3$ で2個消す
• $\div 2$ で1個消す

とした場合の

• 割る数 = $7 \times 3 \times 2 =$ $42$

が最大です。

• 残る時間 = $5040 \div 42 =$ $120$

となり、答えは120秒となります。

検算:

120の20以下の約数を調べます。

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20

と、丁度11個です。

電灯を5個消すときに割る数が2番目に大きい組み合わせを探します。

先程と同様、$\div 2$ で1個消すのが最優先です。

そうなると残り4個を 2+2 に分割する方法は先程「1回目」の時に使ってしまったので$\div 5$ で4個消すしかありません。

• 組み合わせ：$\div 5$ で4個消し、$\div 2$ で1個消す、計5個
• 割る数 = $5 \times 2 =$ $10$
• 残る時間 = $5040 \div 10 =$ 504秒後

となり、答えは504秒となります。

検算:

504の20以下の約数を調べます。

1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 18

と、丁度11個です。