連載

あなたはビルゲイツの試験に受かるか?
バックナンバー

その48 着眼点が解答スピードを決める
前号へ
  次号へ

 基礎的な論理思考の頭脳作りさえできていれば、いろんな問題の解決も簡単にできるようになるということは、すべてのパズルにおいて共通して言えることですが、前問ではトランプの確率の問題と共通して、誕生日が同じである確率も簡単に出すことができました。
 皆さんの中には、これまでに宝くじを買ったことのある人も多いと思いますが、全部で○○○枚発行されている宝くじを◎◎枚購入し、そのうちどれかが当る確率も、このトランプの問題と同じ解き方で、簡単に求めることができるということです。

 さて今号の設問は、コンピューター原理の一部を応用したとも言えそうな解答となる問題ですが、それでは解説に入ります。


問題 設問48 箱がx個とy枚の1ドル札がある。お金を箱に封入し、どの箱も開けず箱を渡すだけで、0ドルからyドルまで、求められた総額を出せるようにしなさい。そのとき、xとyにはどんな制約があるか。

箱と1ドル札

 当連載を通して、各問題解決の手がかりや糸口、突破口はどこにあるのか、その着眼点を探ることで正解に至る必然性というところに力点を置いており、あくまでもその必然性を丁寧に解説することで皆さんの「考える頭脳作り」を支援するよう心がけていますが、では本問の着眼すべきところはどこでしょうか。
 それはこれまでの設問と大きく違うところ、つまり本問にはxとかyなどといった記号だけが示され、最初から具体的な数字が示されていないという点です。そんなことは当然言われるまでもない、ということかもしれませんが、その重要な意味に気づくかどうかなのです。
 つまり「この問題は、一般化、普遍化ができますよ」と、種明かしとなるヒントを与えているということです。

 なぜそれが種明かしなのか。そこで過去の設問の中で解説した一般化や普遍化したものを思い出してみてください。
 その1つ、「1枚だけ他のものより軽い硬貨が混じっている、外見上区別のつかない8枚あるいは9枚の硬貨を天秤にかけ、最小の回数でそれを見分ける方法」の設問33がよい例で、意図的にその解説を設問34のほうに回していますが、そこでは「最初に与えられた枚数がx枚だとすると、3n-1 <x ≦3nから、n 回がすぐに出てくる」という一般化の話をしています。

 ではこの一般化、普遍化が、どこで重要な意味を持ち、種明かしのヒントを提供してくれるかといえば、数字がどんなに大きなものであろうと、数字の少ないあるいは数字の小さい段階をしっかりと分析すれば、そこに必ず一般化への規則性が存在するということを示唆しているからです。
 このことは、長方形のテーブルに10円玉を置いていく設問22や、100個のロッカーをトグル設問43などの他の例でも、数の少ないケースを分析することにより、そこに存在する規則性を見つけることができました。
 このことから当設問48でも、出だしの段階であれこれいろんなことを考えなくても、1ドル紙幣の枚数が10枚くらいまでのところを分析してみれば、そこに必ず一般化への規則性が見つかるということです。

 では、具体的に詳細へと入ってまいります。
 たとえば、まずここに1ドル紙幣の枚数が10枚で、10ドルあるとします。そこで1、2、3、・・・10ドルと1ドルから10ドルまでのすべての額を出すための1つの方法としては、10個の箱を用意し、それらすべての箱に1ドル紙幣を入れておけば10ドルまでの求めらる金額どれでも、その数だけの箱を渡すことで解決します。がしかし、当然のことながらビル・ゲイツはこんな解答を望んでいるわけではありません。
 過去の設問、たとえば5個の箱の中、1箱だけ他のものより軽い玉が詰まっているその箱を見分ける方法を問う設問17でも見ましたように、解答にいくつかの方法があるなら、その中で一番時間や労力や費用などの手間のかからない解答を求めているということです。
 まずこのことを頭に入れておかねばなりません。

 そこで次にビル・ゲイツの言う「よ〜く考えよ」を念頭に、改めてこの設問の箱の意味するところを考えてみますと、その役割は紙幣をブロックで分けるということです。
 つまりこのブロックに分けること、さらにどんな数でもすべての数が表現できることを突き詰めていきますと、必然的に○○○進法に行き着くことになると思います。
 すなわち二進法や三進法の20、21、22、23、30、31、32などはそれぞれブロックであり、それらを組み合わせることにより、すべての数が表現できます。

 そこで二進法ならば、20、21、22、23の4つのブロックが1つずつあれば、その組合せで1から10までのすべての数を表現できますが、三進法だとどうしても30、31、32それぞれのブロックが2つ、2つ、1つ、合計5つのブロックがないと表現できません。このことからも、これ以降の四進法の先では5つ以上のブロックが必要なことは想像つくと思います。つまり箱の数としては二進法による分け方が一番少ないということです。
 こうして設問のyが10枚の紙幣ならば、箱に入れる紙幣の数を二進法による20、21、22、23、つまり1、2、4、8枚と分けて封入しておけばいいことがわかります。

箱と1ドル札

 ところがこの場合、箱の中に入っている紙幣の合計は15枚であり、このことはあらかじめ10枚以上の15枚の紙幣でこの4ブロックを準備しておかないと、求められる10ドルまでのすべての金額を出すことができない、ということです。ここで壁にぶつかることになります。
 そこで他にいい方法があるのではないかと思案することになるわけですが、ここに至り気になってくるのは、設問の中のもう一つの問い「そのとき、xとyにはどんな制約があるか」に出てくる「制約」という言葉ではないかと思います。これは一体何を意味しているか。それが壁を乗り越えるヒントになるのか。

 では、xである箱の数、つまりブロックの数をこの二進法で考えてみることにします。
この二進法だと、必要なブロックの数を算出するには時間がかからないことがすぐわかります。というのも、それは二進法の表記そのものだからです。
 つまり十進法で1、2、3、4・・・は、二進法ではそれぞれ(1x20)、(1x21+0x20)、(1x21+1x20)、(1x22+0x21+0x20)・・、すなわち1、10、11、100のように表記する方式ですから、必要なブロックはこの中の1とフラッグが立っているところで、必要な箱の数は、当初の数までのブロックフラッグのネット合計数で出てくるからです。

 こうして十進法の1、2、3、4、5、6、7、8、9、10は、二進法で1、10、11、100、101、110、111、1000、1001、1010で表記されますから、当初の紙幣が10枚あるとき、1から求められる数の枚数まですべてを出すために必要なブロックすなわち箱の数は、順に1、2、2、3、3、3、3、4、4、4個となることがわかります。
 このことから、箱の数が増えていく境目は、十進法で2、4、8のところ、いわゆる二進法で桁が上がるところ、つまり2の「べき乗」のところであることがわかるとともに、その「べき乗」の数値そのものが、必要な箱の数と密接な関係を持つ
こともわかってきます。
 二進法など、これまでまったく縁のなかった一般の方たちも、2の倍数の数値のところで箱が増えていくというふうに考えていただければ、わかり易いと思います。

 そこでxとyの関係です。yの値からどうやって「べき乗」となっている箱の数xを導き出すかですが、今度はどうしても高校での数学知識、ロガリズムのlog表現が必要のようです。
 このlogを用いると、具体的に2=3ではx=Log23と表現するように、一般にa=bはx=Logabと表しますので、当設問の箱の数xと紙幣の枚数yの関係はx=log2yのように表せます。
 こうして、紙幣1〜10枚それぞれに必要な先ほどの箱の数1、2、2、3、3、3、3、4、4、4個は、x=(log2yの整数値)+1として導かれることがわかります。yの値次第ではlog2yが小数点となり、きっちり整数にならないことがありますので、その整数部分を取って(log2yの整数値)としたわけです。

 ここで先ほど出てきた壁をもう一度考えてみます。たとえば、最初ここに1ドル札7枚の紙幣があるとします。するとx=(log27の整数値)+1=3で、3個の箱・・・1枚(20)入りの箱1個、2枚(21)入り箱1個、4枚(22)入り箱1個・・・があれば、それらの組合せで1から7ドルまでのどの金額でも出すことが出きますが、しかし1枚増えて8ドルになった途端、新たに8枚(23)入り箱が必要になり、それまで紙幣合計が7枚あればこと足りていたものが、1から8ドルまでのすべての要求に応えるためには、合計15枚の紙幣がどうしても必要となって、一気に8枚不足してくるのです。

 このことは何を意味しているのかと言えば、yが2のべき乗の境目となる1つ手前の2−1枚とぴったり一致すればそのまま二進法で、それ以外であれば2−1枚からy枚を引いた不足分を足して2−1枚にし、それを二進法で箱に入れておく必要があるということです。

 しかし、本当にそうか。
 ここで再度、前の例を用いて具体的で丁寧な説明をします。yが7枚のときx=(log2yの整数値)+1からxは3で、計算式23−1=7枚とぴたり一致しますので、20、21、22それぞれのブロックが1個あれば1から7ドルすべてを出せますが、もしもyが10枚なら、当然この計算式で出る7枚と一致しませんので、追加枚数が必要となります。しかし、ここで一考。

 7ドルまでをすべてが出せて、10ドルまでは出せない。厄介者は残りの10−7の3ドルです。7ドルまではすべてを出せるのに・・・と、ここではっと気づくはずです。当然ですが、この厄介者を除いてしまえばあとは自由に出せるということを。つまり、この厄介者を1つの箱に閉じ込めてしまえばいいのです。
 求められるドルが10なら、この3と、残りの7を20、21、22の二進数で出せます。9ドルでも8ドルでも、この3を渡したあと、それぞれ残りの6と5を同様にこれら二進数で出せるということです。

解説図1
解説図2

 この基本形がわかれば、あとはyが100でも1000でも同様な分け方をしておけばよいことがわかります。
 当設問の背景は、いかに早く二進法を思い付くか、そしていかに早くxとyの関係式を作り出せるかという論理思考の問題です。

 では、解答です。


正解 正解48 まず、合計がy枚に一番近くなる二進法で分け、それぞれを箱に入れる。この箱をA群とする。さらに残りの枚数が出れば、それをまとめてもう1つの箱、Bに入れておく。そしてまず最初に、このBの箱を渡し、あとは求められた金額からこのBに入っている金額を引いたCドルを、A群の箱の組合せでもって渡せばよい。このときyとxの関係は、x=(log2yの整数値)+1である。


 では、出題背景を考えながら、次のビル・ゲイツの設問を解いてみてください。


問題 設問49 50組の夫婦のいる村の男全員が、不貞をはたらいている。小さな村ゆえに、村の女はみな、自分の夫以外の男が不貞をはたらけば、即座にそれがわかる。しかし、自分の夫が不貞をはたらいてもわからない。村の厳しい掟では、自分の夫が不貞をはたらいたことを証明できる女は、その夫を即日殺さなければならないとしており、この掟に逆らおうなどと思う女はいない。ある日、決して過ちを犯さないことで知られる女王が、この村を訪れた。そして女王は、少なくとも1人の夫が不貞をはたらいていると宣告した。そこでこの村はどうなるか。


前号へ   次号へ


 ビル・ゲイツの出題問題に関しては、HOW WOULD YOU MOVE MOUNT FUJI ? (Microsoft’s cult of the puzzle. How the world’s smartest companies select the most creative thinkers. )By William Poundstore の原書や、筆者の海外における友人たちの情報を参考にしています。
 また連絡先不明などにより、直接ご連絡の取れなかった一部メディア媒体からの引用画像につきましては、当欄上をお借りしてお許しをいただきたく、よろしくお願い申し上げます。

執筆者紹介


執筆者 梶谷通稔
(かじたに みちとし)

テレビ出演と取材(NHKクローズアップ現代、フジテレビ、テレビ朝日、スカパー)

出版

連載

新聞、雑誌インタビュー 多数

※この連載記事の著作権は、執筆者および株式会社あーぷに帰属しています。無断転載コピーはおやめください

Page top