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

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

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

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

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

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

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

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

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

　では、ｘである箱の数、つまりブロックの数をこの二進法で考えてみることにします。
この二進法だと、必要なブロックの数を算出するには時間がかからないことがすぐわかります。というのも、それは二進法の表記そのものだからです。
　つまり十進法で1、2、3、4・・・は、二進法ではそれぞれ（1ｘ2⁰）、（1ｘ2¹＋0ｘ2⁰）、（1ｘ2¹＋1ｘ2⁰）、（1ｘ2²＋0ｘ2¹＋0ｘ2⁰）・・、すなわち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の倍数の数値のところで箱が増えていくというふうに考えていただければ、わかり易いと思います。

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

　ここで先ほど出てきた壁をもう一度考えてみます。たとえば、最初ここに1ドル札7枚の紙幣があるとします。するとｘ＝（log₂7の整数値）＋1＝3で、3個の箱・・・1枚（2⁰）入りの箱1個、2枚（2¹）入り箱1個、4枚（2²）入り箱1個・・・があれば、それらの組合せで1から7ドルまでのどの金額でも出すことが出きますが、しかし1枚増えて8ドルになった途端、新たに8枚（2³）入り箱が必要になり、それまで紙幣合計が7枚あればこと足りていたものが、1から8ドルまでのすべての要求に応えるためには、合計15枚の紙幣がどうしても必要となって、一気に8枚不足してくるのです。

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

　しかし、本当にそうか。
　ここで再度、前の例を用いて具体的で丁寧な説明をします。ｙが7枚のときｘ＝（log₂ｙの整数値）＋1からｘは3で、計算式2³−1＝7枚とぴたり一致しますので、2⁰、2¹、2²それぞれのブロックが１個あれば1から7ドルすべてを出せますが、もしもｙが10枚なら、当然この計算式で出る7枚と一致しませんので、追加枚数が必要となります。しかし、ここで一考。

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

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

　では、解答です。