Weekend Mathematics／問題／問題97

９７．２００５年の問題

2005個の箱が横１列に並んでいます。これらの箱には、左から順に１，２，３，・・・・，２００４，２００５と番号がついています。いま、このうちの１つの箱に「当たり」と書いた紙が入っていて、その箱より左側にあるすべての箱には「右」と書いた紙が、右側にあるすべての箱には「左」と書いた紙が入っています。このとき次の問いに答えなさい。

（問１）
B君がこれらの箱の中から「当たり」と書いた紙を確実に取り出すまでに、最低何個の箱を開けなければならないでしょうか。

（問２）
このとき、一番はじめに開ける箱の番号は、何番から何番の範囲でなければならないでしょうか。
ただし、開ける箱の選び方は、開ける箱の数が最も少なくなるよう最善の選び方をするものとします。

解答・その1

（ペンネ−ム：Mr.X）

問１．１０２４≦２００５≦２０４７　なので　１１回
（２≦箱数≦３　では　２回．…．）
問２．２００５＝９８２＋１０２３　だから　
９８２（右に１０２３個）〜１０２４（左に１０２３個）

　

解答・その2

（ペンネ−ム：内海　育）

（答）
問１　11個
問2　982番目から1024番目

（過程）
最後に1個残ればそれが当たりゆえ開く個数１
1個残すには最大3個残せばよく、開く個数は２個
最大3個残すには最大7個残せばよく、開く個数は計３個
最大7個残すには最大15個残せばよく、開く個数は計４個
最大15個残すには最大31個残せばよく、開く個数は計５個
最大31個残すには最大63個残せばよく、開く個数は計６個
最大63個残すには最大127個残せばよく、開く個数は計７個
最大127個残すには最大255個残せばよく、開く個数は計８個
最大255個残すには最大511個残せばよく、開く個数は計９個
最大511個残すには最大1023個残せばよく、開く個数は計10個
最大1023個残すには982番目（左に981個、右に1023個）から1024番目（左に1023個、 右に981個）を開けばよく、開く個数は計11個

解答・その3

（ペンネ−ム：やなせ）

問１
２００５から中央を開けるとしますねどっちにしても残りは１００２個
つぎの真ん中を開けるとして多い方は５０１個・・・・
と行けば２５０→１２５→６２→３１→１５→７→３
これからは絶対に２回で当たりの札？を手に出来るので、１１回ですかな。

問２
前回の答えから一歩手前の数を３と考えて、そこからから行くと
３＊２＋１＝７、７＊２＋１＝１５、
１５＊２＋１＝３１、３１＊２＋１＝６３、６３＊２＋１＝１２７、
１２７＊２＋１＝２５５，２５５＊２＋１＝５１１、５１１＊２＋１＝１０２３
１０２３残れば１０回で当たりになるので最初に開ける最大の場所は１０２４番目です。
又最小の場所は全体の数２００５から１０２３を引いた９８２番目になります。

解答・その4

（ペンネ−ム：杖のおじさん）

答え　１１個目　左から９８２番目以上１０２４番目以下の箱を開けます。

この問題は箱を開けると右とか左と矢印があることで開けた箱の左か右の一方に分岐して行く事が出来ます。従って絞り込んで１箱に出来れば見つけることが出来るのです。 従って次の式で見つけるまでの箱の数を数えることが出来ます。 もし、矢印が入っていなかったら予想はできません 左から中央の箱を開ける。一回目２００５÷２＝１００２．５　なので１００３番目 左に１００２箱残る、右に１００２個残る ２回目、左なら１００２÷２＝５０１なので左から５０１番目を開ける。左に５００個残る、右に５０１個残る。これを繰り返して最後の１箱まで絞り込みます。

今回もCASIO　FX-８７０PとFX-８９０P　でBASICのプログラムを次のように作りました。

10 CLS:INPUT”ハコノ　カズ”;A
20 B=INT(-A/2)*(-1)
30 FOR X=1 TO 50
40 IF A=1 THEN PRINT  X;“コメ”:GOTO 70
50 A=INT(A/2)
60 NEXT X
70 C=2^(X-1)-B
80 D=B-C
90 E=2^(X-1)
100 PRINT D;”バン　イジョウ”;E;”バン　イカノ　ハコデス”
110 IF INKEY$=”” THEN 110
120 GOTO 10

プログラムの中の20行は箱の数を半分に割って端数が出たら切り上げています。 上のプログラムを実行しますと　ハコノカズ？　と聞いてきますので２００５と入力してEXEキーを押しますと　１１コメ　９８２バン　イジョウ　１０２４バン　イカノ　ハコデス　と表示されます。 EXEキーを押すと１０行に戻りますので　ハコノカズ？　と聞いてきます。 いろいろ入力して見てください。 注VisualBasicはGOTOが使えませんので同じにするには上のプログラムの70行から120行までをNEXTの前に組み込みます。考えて見てください。２月に発表いたします。 勉強のために組み込むので、私はBASICでは上の組み方でしています。行数を10行間隔にするのも意味があります。CASIOではRENUMでソートされます。

エクセル（ワードでも作れます）のユーザーフォームでも作りました。次のフォームです。

このフォームの作り方は 私のホームぺージで解説いたします。

解答・その5

（ペンネ−ム：巷の夢）

(問１)
個数を絞り込んでいくのが定石でしょうから、まず対象を半分にすることを考えます。次に又半分にすることを考えます。この様に半分々、半分と考えていけば最終的には一つに絞り込むことが可能です。勿論、運が良ければこの仮定の途中で｢当り｣に至ることができますが、それはあくまでも幸運と考え、まず1003、次に502という様に選んでいく工程を繰り返せば、最悪の場合でも11個選べば｢当り｣に辿り着けます。

(問２)
全問より11個選べば｢当り｣に辿り着けることが分かっていますので、今度は逆に辿っていけば最初に選ぶ番号に行き当たることが分かります。11回目の選択で｢当り｣に至るわけですからこのとき机上に残っている枚数は2枚です。するとこの前の過程で机上に残っている枚数は3枚であったことが分かります。この考え方で、更にその前の枚数を考えると7枚になります。後は同様に考え、15、31・・・となります。ここで10回前を考えると1023となります。因って最初に選ぶ番号は一つ右の1024で良い事が分かります。以上の考えは左から順番に並んでいる数で選択しました。これと全く同様に右側の数の並びを考えると、2005−1023＝982となりますので、求めるものは982〜1024となります。

解答・その6

（ペンネ−ム：三角定規）

(問1) 11回 ( 2¹⁰−1＜2005≦2¹¹−1 より，説明は下で）
(問2) 983番目から1023番目
　　　　(コメント：１つずれているかな？　by　Junko）

《一般解》
正整数Nに対し，2^m-1−1＜N≦2^m−1 を満たす正整数mが一意に定まる。
m＝[log₂(N＋1)] ([ ] はガウス記号)
題意が求める「“当たり”を見つける最善手の手数」は，この m である。

《証明》
(�T) N＝1，m＝1 のとき，明らかに1回でわかる。
駄目押しながら，N＝3，m＝2 のとき
(1回目) 2番目を開け，それが「当たり」ならばそれで終わり。
そうでなければ，2番目には“左”もしくは“右”と書いてあるはずなので指示された方を開ければ（2回目で）「当たり」を見つけることができる。

(�U) m＝k のとき命題の成立を仮定する。
すなわち，「箱が最大N＝2^k−1 個ならば，k回で当たりが見つけられる」を仮定する。
このとき，N＝2^k+1−1 個の箱に対し， (1回目) 左に2^k−1 個，右に 2^k−1 個残し中央の2^k 番目を開ける。それが「当たり」ならばそれで終わり。
そうでなければ，“左”もしくは“右”であるが，どちらが出ても仮定より残りはk回で見つけられる。 よって，(最善手で）k＋1 回で見つけられる。

(�V) 以上で帰納法が完結し，題意は示された。

解答・その7

（ペンネ−ム：夜ふかしのつらいおじさん）

答は、（問１）１１回、（問２）９８２番から１０２４番です。

この問題を考えるには、やさしい場合から始めます。

箱が１個のときは、１回です。
箱が２個のときは、２回です。
箱が３個のときも、２回です。（初めに２番の箱を開けます）
箱が４個のときは、３回です。（初めに２番か３番の箱を開けます。仮に２番の 箱を開けたとすると、右には２個の箱があるので２個の場合を参照します）
箱が５個のときも、３回です。（初めに３番の箱を開けます）
箱が６個のときも、３回です。（初めに３番か４番の箱を開けます。仮に３番の 箱をあけたとすると、右には３個の箱があるので３個の場合を参照します）
箱が７個のときも、３回です。（初めに４番の箱を開けます）
箱が８個のときは、４回です。（初めに４番か５番の箱を開けます。仮に４番の 箱を開けたとすると、右には４個の箱があるので４個の場合を参照します）
・・・・

箱が１個のときは、１回。
箱が２，３個のときは、２回。
箱が４，５，６，７個のときは、３回。
箱が８，９，１０，１１，１２，１３，１４，１５個のときは、４回。
・・・・

開ける回数がｋ回のとき、最大の箱の個数は２^k−１個です。
１回のときは、１個です。つまり、２¹−１です。
２回のときは、３個です。これは、中央の１個と、その両側に１回のときの１個 ずつです。つまり、

　　　２×１＋１＝２＋１＝(２−１)(２＋１)＝２²−１です。

３回のときは、７個です。これは、中央の１個とその両側に２回のときの３個ず つです。つまり、

　　　２×(２×１＋１)＋１＝２²＋２＋１ ＝(２−１)(２²＋２＋１)＝２³−１です。

４回のときは、１５個です。これは、中央の1個とその両側に３回のときの７個 ずつです。つまり、

　　　２×(２×(２×１＋１)＋１)＋１＝２³＋２²＋２＋１ ＝(２−１)(２³＋２²＋２＋１)＝２⁴−１です。

また、開ける回数が(ｋ＋１)回のとき、最小の箱の個数は２^k個です。 まとめると、ｋ回で開けることのできる箱の個数は、２^k-1個から２^k−１個 です。

さて、

　　　２００５＝１０２４＋５１２＋２５６＋１２８＋６４＋１６＋４＋１ ＝２¹⁰＋２⁹＋２⁸＋２⁷＋２⁶＋２⁴＋２²＋１

なので、２¹⁰＜２００５＜２¹¹−１となり、（問１）は１１回です。

ところで、ｋ＝１０回のときの箱の最大の個数は２¹⁰−１＝１０２３です。
だから、1回目は左に１０２３個あるようにするか、右側に１０２３個あるよう にすればよいのです。
つまり、左に１０２３個のときは１０２４番目、右に１０２３個のときは、
２００５−１０２３＝９８２番目の箱を開ければ良いのです。
つまり、（問２）は、９８２番目から１０２４番目の範囲なら良いことになりま す。

解答・その8

（ペンネ−ム：ＦＩＶＥＩＬＡＮＤ）

答え　問1　11個　　問2　982番から1024番まで

考え方

問1
一回開けるごとに半分に減っていきます。

　　　　2¹⁰＜2005≦2¹¹

したがって、11個となる。

問2
問1より右側も左側も2¹⁰よりも小さな個数でなければならない。
これを満たす最小の箱の番号はそれぞれ

　　　　2005−（2¹⁰-1）＝982、2¹⁰＝1024

解答・その9

（ペンネ−ム：なか）

２００５が目に止まったので考えてみました。
バイナリーサーチ（二分探索）の問題ですね。

・箱が１個の場合は１回で当たる。
・箱が３個の場合は最初に真ん中を開ければ、最悪でも２回で当たる。
・箱が７個の場合は最初に真ん中を開ければ、外れても候補は３個に絞られるので、最悪でも３回で当たる。
・一般に箱が２^ｎ−１個の場合は最悪でもｎ回で当てられる。
・このようにして箱が１０２３個なら１０回で当てられる。
・２００５−１０２３＝９８２なので９８２を開けるととぎりぎり１１回で当てられる。
・同様に１０２４を開けた場合もぎりぎりだいじょうぶ。

答　（問１）１１回　（問２）９８２〜１０２４

解答・その10

（ペンネ−ム：Toru）

１回で確実に決められるのは１個
２回で確実に決められる最大値は３個
３回で確実に決められる最大値は両側に３個ずつ残したまん中を選べば2x3+1=7
これらからk 回で確実に決められる最大値を2^k-1と予想すると （k＋１）回で確実に決められる最大値は両側に（2^k-1）ずつ残したまん中を選ぶと 考えてとして2x(2^k-1)+1=2^k+1-1でこれが正しいことが分かる。
したがって「箱の数が2^k-1〜2^k-1の時、確実に「当たり」を取り出すためには、 最低k回箱をあけなければならない」と考えられる。

（問１） 2¹⁰=1024, 2¹¹=2048 より11回
（問２） １個箱をあけた後、「右」と出ても「左」とでても残りが2¹⁰-1=1023以下 になるように選べばよい。
2005-1023=982より982番〜1024番

解答・その11

（ペンネ−ム：やんま）

１．ｎは箱を開ける回数、ｌはｎ回開けて「当たり」を確実に取り出せる箱の最低数、ｍはｎ回開けて「当たり」を確実に取り出せる箱の最大数とすれば、次の表の通りとなる。
箱は２００５個であるからｌ＝１０２４とｍ＝２０４７の中にある。従って最低１１個の箱を開ければよい。 範囲は２番目に開ける時、残っている箱が１０２３個以下であればよいから ２００５−１０２３＝９８２、即ち９８２番目を開ければ右側に１０２３個のこることになる。また１０２４番目の箱をあけると左側に１０２３個のこることになる。 従って一番はじめに開ける箱の番号は９８２から１０２４番の範囲となる。

答え　１．最低１１個、　２．９８２番〜１０２４番

n	l	m
1	1	1
2	2	3
3	4	7
4	8	15
5	16	31
6	32	63
7	64	127
8	128	255
9	256	511
10	512	1023
11	1024	2047
12	2048	4095

２．ｎやｌなど記号の意味は１．と同じ
任意の箱の数ｘからｎを求めるには

　　　　　　　　 [ ]はガウスの記号

ｌは倍々に増えていくので、求める式は ｌ＝２^ｎ−１
一番はじめに開ける箱の番号のうち小さい方をMin、大きい方をMaxとすると

　　　Min＝ｘ−（ｌー１）
　　　Max＝ｌ　　　　　　　　で求めることができる。

ｘに２００５を代入して計算するとｎ＝１１、ｌ＝１０２４
　　　　Min＝２００５−（１０２４−１）＝９８２
　　　　Max=１０２４

答え　１．最低１１個、　２．９８２番〜１０２４番

解答・その12

（ペンネ−ム：蜘蛛の巣城）

箱の中の紙片を取り出す１回目の試技から「当たり」を引く可能性はありますが、「確実に、なるべく少ない試技の回数で」引くためには、中央あたりから手を付けるべきでしょう。仮に真ん中の箱を開く場合、次の３つのケースに分類できます。

　�@ 2ｎ＋1個の箱の真ん中を開き「右左」の指示に従って ｎ 個の箱が残る。
　�A 2ｎ 個の箱の真ん中の2個のうち、1個を開き ｎ−1 個が残る。
　�B 2ｎ 個の箱の真ん中の2個のうち、1個を開き ｎ 個が残る。

上の３つのケースのうち、�Bの場合に残る箱の比率が最も大きく試技者には不利です。このケースが連続したときに、何回の試技が必要か考えてみるのがよいでしょう。明らかに2ｎ 個の箱に対して ｎ＋1 回の試技が必要です。当たり紙片の入っている箱の判別だけなら ｎ 回の試技で十分ですが、確実に取り出すにはもう１回の試技が必要です。試技者にとって最も不利な条件で考えたのですから、次の定理の成立は明らかです。

　　　　2^ｎ≦箱の個数＜2^ｎ＋1　　　のとき　ｎ＋1 回の試技が必要

本題の場合は次のように表されます。

　　　　1024＝210＜2005＜211＝2048　だから　　11回の試技が必要

箱の総数 2047個までは11回の試技で取り出し可能ですが、この場合1024番目の箱がちょうど真ん中です。1回目の試技は必ずここでなければなりません。2005個の箱の場合、条件は楽になりますが、1024番目の箱が条件の許す端の箱です。2005番目を1番目としてすべて反転させると、1024番目は982番目に変わります。
即ち、982番目から1024番目までの43個の箱が第1手の許される箱です。

解答・その13

（ペンネ−ム：小学名探偵）

答え　(問1) １１個　(問2)　９８２以上１０２４以下

どの箱に当たりが入っていたとしても、Ｍ個の箱を開けるまでに（Ｍ手以内に）、必 ず当たりが引かれる。 （運が悪くても、Ｍ回目に開ける箱には当たりが入っている）このＭを最小にするよ うな選び方が、最善の選び方ですね。
いま、最小個数をＮ、最初に開ける箱の番号をｘとします。
箱の個数が１の場合、あきらかにＮ＝１，ｘ＝１
箱の個数が２の場合、あきらかにＮ＝２，ｘ＝１か２
箱の個数が３(=2²-1)の場合、最初に真ん中の箱を開けたとき（ｘ＝２のとき）の み、Ｎ＝２になります。
よって、Ｎ＝１のとき、箱の個数の最大値＝１＝2¹ -1です。 いま、Ｎ＝ｎのとき、箱の個数の最大値＝2ⁿ - 1　と仮定すると、 Ｎ＝n+1のとき、箱の個数の最大値＝2ⁿ⁺¹ -1 になります。なぜなら、

a) 箱の個数が2ⁿ⁺¹ - 1のとき、 真ん中の箱、ｘ＝2ⁿを開ければ、左右に2ⁿ - 1個の箱が残ることから、Ｎ＝n+1に なるような、開ける箱の選び方が存在し、
b) 箱の個数が2ⁿ⁺¹ - 1より１つでも多いと、どの箱 を最初に開けても、左右のどちらかに2ⁿ- 1個より大きな個数の箱が残ることからＮ＞(n+1)になる、か らです。

以上から、N=nになる（ｎ手で解決する）、箱の個数の最大値が2ⁿ - 1であること、 よって、箱の個数Ｂが、

　　　　2^n-1≦Ｂ≦2ⁿ - 1

のとき、Ｎ＝ｎになることが示されました。
つぎに、箱の個数Ｂが、2^n-1≦Ｂ≦2ⁿ - 1のとき、すなわち

　　　Ｂ = 2ⁿ - s, ただし、1≦s≦2^n-1

のとき、Ｎ＝ｎにするために、最初に開けるべき箱の番号ｘの範囲を決定しましょう。
ｘより左側にある箱の個数（＝ｘ -1）が、2^n-1 -1を超えないかぎり、そのなかから、 Ｎ≦n -1　で当たりの箱（もし左側にあれば）にアクセスできます。よって、ｘ≦2^n-1 同様にして、ｘより右側にある箱の個数(＝2ⁿ - ｓ- ｘ)が、2^n-1 -1を超えない かぎり、そのなかから、 Ｎ≦n -1　で当たりの箱（もし右側にあれば）にアクセスできます。よって、

　　　　2^n-1 - (ｓ-１）≦ｘ

（左側にある箱の個数と右側にある箱の個数のうち大きい方≧2^n-1　なので、Ｂ に対するＮ＝n です） 以上から、ｘの範囲は、

　　　　2^n-1 - (ｓ-１）≦ｘ≦2^n-1 （ｘは2^n-1以下、連続するｓ個の整数値を取る）

になります。

（１）箱の個数2005 = 2¹¹(=2048) -43　から、Ｎ＝１１個
（２）最初に開ける箱の番号ｘは、2¹⁰ - 42=982≦ｘ≦2¹⁰=1024

箱の個数Ｂを２進数で書くと、１ならＮ＝１、１０か１１ならＮ＝２・・・のように なります。
つまり、１が立っている最も大きな桁番号（Ｂの桁数）がＮの値を与えます。 また、

11111=1111 + 1111 +1（全体＝右側の箱の個数＋左側の箱の個数＋開けた１つの箱）
1111=111+111+1（1111＝111の左シフト+１，　A(n)=2*A(n-1)+1）
111=11+11+1
11=1+1+1
1=0+0+1

このようなことから、高々、Bの桁数（ｎ個）の箱を開ければ必ず当たりが得られるような、 Bの最大値＝”ｎ個のオール１の２進数”になること、箱の個数がオール１の２進数で表される場合、 操作のたびに、真ん中の箱が開けられることが容易に分かります。

2005を２進数で表すと、11111010101

ｘの最大値は、10000000000
(Ｂ(＝11111010101)の最上位ビット以外のビットをクリアした値）
ｘの最小値は、11111010101 - 10000000000 +1=1111010110
(Ｂ(＝11111010101)の最上位ビットをクリアして１を加えた値)になります。

N=nのときに、箱の個数の最大値＝2ⁿ - 1　であることの別証明

　　　　○｜○｜○｜○｜・・・○｜○

上の図において、”○”は「箱」、仕切の”｜”は当たりの箱が右側の箱群のなかに あるか、 左側の箱群の中にあるかを示す情報です（”｜”を引くとこの情報が得られます）。 １つの”｜”を引いたとき、右側にある箱の個数、左側にある箱の個数を「次の検索 範囲候補」と呼ぶことにします。 左右にある「次の検索範囲候補」のうち、引いた”｜”の情報が指す方が次の検索範 囲です。 次の検索範囲が１であれば、当たりの箱が見つかったことになります。１つの”｜” に関して、 右側にある箱の個数と左側にある箱の個数のうち、大きい方MAXは、ワーストケース における次の検索範囲を定めます。ここに、

　　　　　次の検索範囲（ワーストケース）／前の検索範囲≧１／２　　　　式（１）

等号が成立するのは、”｜”の本数が奇数で、真ん中の”｜”が存在し、それを引い たときです。
B=2ⁿの場合、順次、真ん中の”｜”を引いて次の検索範囲を半分に絞り込んでいく ことができます。 すると、ｎ本の”｜”を引いたときに、次の検索範囲＝１になって当たりの箱が特定 されます。 式（１）から、この2ⁿは、ｎ本の”｜”を選択するときに検索できる箱の個数の最 大値になることがわかります。 このモデルにおいて、

　　　　　”｜”の個数＝”○”の個数−１　　　　　　　　　　　　　　　式（２）

ここで、”｜”を紙が入った箱に置き換えると、本問のモデルになります。
先のモデルにおける最大値＝2ⁿ は、このモデルでは、式（２）から、

最大値＝2ⁿ+2ⁿ -1＝2ⁿ⁺¹ -1
になります。このとき、N＝ｎ＋１です。

N=nに対する、箱の個数の最大値ＭＡＸは、次のようにしても示されます。
ｓ_１）（○｜○）　”｜”は開箱候補、”○”は左右の箱群、（　）は検査ユニット
ｓ_２）（○｜○）（○｜○）　ステップ２では、開箱候補数＝２
．．．．．．．．
開箱候補数を２進数で書くと、ｓ_１）１，ｓ_２）１０， ｓ_３），．．．ｓ_n）１０．．．０（ｎ桁）になります。
ここに、開箱候補に含まれる箱の個数は、１か０です。
あるステップｎにおける開箱候補に含まれる箱の個数の総和が１以上であり、次のス テップ（ｎ＋１）における開箱候補に含まれる箱の個数の総和が０であるとき、検索 はステップｎで完了します。以下、検索はステップｎで完了するとします。
このモデルでは、遅かれ早かれ、どの箱にも開箱候補のラベルが付けられることにな るので、ステップ１からステップｎまでのすべての開箱候補に含まれる箱の個数を数 え上げれば、与えられた箱の総数になります。
各ステップについて、開箱候補に含まれる箱の個数の最大値＝開箱候補の個数 であることから、Ｎ＝ｎに対するＭＡＸは、

ＭＡＸ	＝ｓ１）からｓｎ）まですべての開箱候補の総和
	＝1+10+100,...,10...0(ｎ桁)＝11...1(ｎ桁)

正解者

ＦＩＶＥＩＬＡＮＤ	やなせ	杖のおじさん
小学名探偵	Toru	巷の夢
夜ふかしのつらいおじさん	Mr.X	なか
三角定規	やんま	蜘蛛の巣城
内海　育

半分、半分と候補が減っていきます。なかさんのご指摘の通り、二分探索の問題です。
2^ｎ−１≦箱の個数＜2^ｎを満たすｎを求めれば、問１の答えがわかります。
逆に言うと、ｎ回で「当たり」にたどり着くには、箱の個数は、2^ｎ−１≦箱の個数＜2^ｎで なければならないということです。
ｎ回で「当たり」にたどり着く最大箱数2^ｎ−１まで遊びがどのくらいあるかといのが問２です。
小学名探偵さんが、詳しく解説してくださいましたが、２進数で表記するとからくりが見えてきます。
（個人的には、このように２進数が見え隠れするような問題、好きなんです・・・。）

E-mail top