ホーム >> その他 >> ドラゴン討伐の魔法の最小使用回数
hide or visible

問題の説明

魔法の使用に関して補足します.まず,ドラゴンは自由に指定できます.一匹でも $2018$ 匹でも $OK$ です.ただし,すべての首がすでに切り落とされているドラゴンは指定できないとします.(もうすでに倒されていると考えてください) また,切り落とせる首の本数 $k$ の範囲は,$1\le k \le $ (指定したドラゴンのまだ切り落とされていない首の本数の最小値) で自由に選べます.
たとえば,最初に全ドラゴンを指定してこの魔法を使用しようとすると,切り落とせる首の本数は $1$ 本となり,全ドラゴンの首を $1$ 本ずつ切り落とすことになります.(よって,$A_1$ だけが討伐できる)

この魔法を $1$ 匹ずつに対して使用すれば,明らかに $2018$ 回使えばすべてのドラゴンを討伐することができます.なので,これよりもっと少ない回数で全ドラゴンを討伐する上手な方法を考えてくださいという問題です.また,その方法が最小回数であるための証明にもチャレンジしてみてください.

ヒント

どのドラゴンを対象にし,何本の首を切り落とすのかでいろいろな戦略が考えられるでしょう.ドラゴンの頭数を少なくした場合の問題について考えてみるのもよい方法かもしれません.ある程度手を動かして考えてみると,意外と少ない回数で討伐可能だと直感するはずです.

たとえば,ドラゴンの頭数が $6$ 匹で,それぞれの首の本数が $1,2,3,4,5,6$ 本のときは次が最小のやり方で,最小発動回数は $3$ 回となります.
二進数表示
実はこれはかなりのヒントです.この例から何か気づくことはないでしょうか.それを $2018$ 頭の場合にどう拡張すればよいでしょうか.

解説

最小回数を求める問題なので,その回数で討伐可能であることと,その回数未満では討伐不可能であることの $2$ つを示す必要があります.それぞれにわけて示します.驚くべきことに,魔法は $11$ 回発動するだけで,全ドラゴンを討伐できてしまうのです!

$11$ 回で討伐が可能であること

まず,首の本数が奇数であるようなドラゴンすべてに対して,$2^0=1$ 本首を切り落とす魔法を発動します.(これにより,すべてのドラゴンの切り落とされていない首の本数は偶数となります) つぎに,切り落とされていない首の本数が $2^2=4$ の倍数でないドラゴンすべてに対して,$2^1=2$ 本首を切り落とす魔法を発動します.以下同様にして,切り落とされていない首の本数が $2^m$ の倍数でないドラゴンすべてに対して,$2^{m-1}$ 本首を切り落とす魔法を発動すると,$11$ 回の魔法の発動ですべてのドラゴンが討伐できます.

$10$ 回以下では討伐不可能であること

$10$ 回魔法を発動したときに切り落とすことができる首の本数の種類がどれだけたくさんあるかを考えます.切り落とす首の本数をそれぞれ $k_1,...,k_{10}$ としましょう.すると,各魔法に対して,その魔法の対象に指定されるかされないかの $2$ 通り考えられるので,多くとも $2^{10}=1024$ 通りしか切り落とすことができません.ドラゴンの首の種類は $2018>1024$ 通りなので,$10$ 回以下では確実に討伐不可能です.

補足

解答の原理はつぎの二進数表示に基づいています.
$2^{10}=1024< 2018< 2^{11}=2048$ なので,$1$ 以上 $2018$ 以下の整数 $n$ は, $$n=a_0\times 2^0+a_1\times 2^1+\cdots +a_{10}\times 2^{10}  (a_1,...,a_{10} \in \{0,1\})$$ という形で一意的に表せます.言い換えれば,$2018$ 以下の整数は,必ず $11$ 桁以下で二進数表示可能です.これがこの問題の本質です.つまり,$1$ から $2018$ までの $2018$ 種類の整数は,二進法を用いると $11$ 種類で十分表現できるということなのです.

解答の戦略を二進数表示で言い換えると次のようになります.
まず,$1$ 〜 $2018$ をすべて二進数表示します.つぎに,一の位が $1$ であるものについて,魔法を発動します.そのつぎは十の位が $1$ であるものについて,魔法を発動します.このように,右の桁から,$1$ を $0$ にかえていくと,$11$ 回ですべての数が $0$ になるのです.