こんにちは。KECの塾・予備校部門，高槻本校の数学・理科担当の川渕です。
先日，某有名動画サイトで面白い話を視聴しました。
「数当てゲーム」の話です。

例えば，A君とBさんの2人でゲームをします。
まず，Bさんが，1～100のうちの1つの数字を頭の中で決めます。
その数字を当てたいA君は，Bさんに質問を繰り返します。
ただし，Bさんは「もっと大きい」「もっと小さい」「正解！」しか答えてくれません。

仮に，Bさんが「65」を思い浮かべたとしましょう。
それを，A君が「1ですか？」「2ですか？」と順番に聞いて行くと，正解するまでに65回も質問が必要になります。
あんまり質問を多くすると，嫌われてしまうかもしれません。
そこで，A君は質問の仕方を工夫して聞くことにしました。

A君「50ですか？」…(1)
Bさん「もっと大きい」
A君「75ですか？」…(2)
Bさん「もっと小さい」
A君「63ですか？」…(3)
Bさん「もっと大きい」
A君「69ですか？」…(4)
Bさん「もっと小さい」
A君「66ですか？」…(5)
Bさん「もっと小さい」
A君「64ですか？」…(6)
Bさん「もっと大きい」
A君「65ですか？」…(7)
Bさん「正解！」

こんな感じで，7回の質問で当てることが出来ました。
Bさんがどんな数字を思い浮かべたとしても，7回以内で当てることができます。
100個も数字があるのに，そんな少ない回数で当てられるなんて不思議ですね。
ポイントは，1回の質問で数の個数を約半分に絞り，次にその残った数のうちの真ん中の数を質問することです。
数の個数が約1/2ずつになっていくので，急激に絞れます。
上の場合だと，数の個数が100個→50個→24個→11個…と少なくなっていきます。
ざっくりいうと，2⁶（64）<100<2⁷（128）なので，7回質問すれば100個のうちのどれかの数にたどり着くことができます。

これは「二分探索」というアルゴリズムの応用例です。
数の個数が増えても，調べる回数はそれほど増えないのも面白いところ。
例えば，誰かの誕生日を知りたいとします。
誕生日は366個ありますが，何回質問すれば正解にたどり着けるでしょうか。
2⁸（256）<366<2⁹（512）なので，9回質問すれば当てることができます。

最近は高校で情報の授業がありますが，私は大学生の時に二分探索を習いました。
そのときは全く印象に残らなかったのですが，実例があると記憶に残りやすいですね。
日々，こんな感じで少しずつですがネタを増やしています。
高槻市役所から徒歩2分の所にある，探索しやすいKEC高槻本校です。

■KEC高槻本校の合格体験談・総集編はこちら

■KEC高槻本校の公式サイトはこちら

新高校1年生向け　1か月無料体験キャンペーン実施中！