Weekend Mathematics問題/問題97



97.2005年の問題

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

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

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






問題の出典


算数オリンピックに挑戦
'00〜'03年度版
算数オリンピック委員会編
2003年第10回算数オリンピックファイナル問題




答えと解説





答えと解説

解答・その1

(ペンネ−ム:Mr.X)

問1.1024≦2005≦2047 なので 11回
(2≦箱数≦3 では 2回.….)
問2.2005=982+1023 だから 
982(右に1023個)〜1024(左に1023個)




 

解答・その2

(ペンネ−ム:内海 育)

(答)
問1 11個
問2 982番目から1024番目

(過程)
最後に1個残ればそれが当たりゆえ開く個数1
1個残すには最大3個残せばよく、開く個数は2個
最大3個残すには最大7個残せばよく、開く個数は計3個
最大7個残すには最大15個残せばよく、開く個数は計4個
最大15個残すには最大31個残せばよく、開く個数は計5個
最大31個残すには最大63個残せばよく、開く個数は計6個
最大63個残すには最大127個残せばよく、開く個数は計7個
最大127個残すには最大255個残せばよく、開く個数は計8個
最大255個残すには最大511個残せばよく、開く個数は計9個
最大511個残すには最大1023個残せばよく、開く個数は計10個
最大1023個残すには982番目(左に981個、右に1023個)から1024番目(左に1023個、 右に981個)を開けばよく、開く個数は計11個



解答・その3

(ペンネ−ム:やなせ)

問1
2005から中央を開けるとしますねどっちにしても残りは1002個
つぎの真ん中を開けるとして多い方は501個・・・・
と行けば250→125→62→31→15→7→3
これからは絶対に2回で当たりの札?を手に出来るので、11回ですかな。

問2
前回の答えから一歩手前の数を3と考えて、そこからから行くと
3*2+1=7、7*2+1=15、
15*2+1=31、31*2+1=63、63*2+1=127、
127*2+1=255,255*2+1=511、511*2+1=1023
1023残れば10回で当たりになるので最初に開ける最大の場所は1024番目です。
又最小の場所は全体の数2005から1023を引いた982番目になります。




解答・その4

(ペンネ−ム:杖のおじさん)

答え 11個目 左から982番目以上1024番目以下の箱を開けます。

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

今回もCASIO FX-870PとFX-890P で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行は箱の数を半分に割って端数が出たら切り上げています。 上のプログラムを実行しますと ハコノカズ? と聞いてきますので2005と入力してEXEキーを押しますと 11コメ 982バン イジョウ 1024バン イカノ ハコデス と表示されます。 EXEキーを押すと10行に戻りますので ハコノカズ? と聞いてきます。 いろいろ入力して見てください。 注VisualBasicはGOTOが使えませんので同じにするには上のプログラムの70行から120行までをNEXTの前に組み込みます。考えて見てください。2月に発表いたします。 勉強のために組み込むので、私はBASICでは上の組み方でしています。行数を10行間隔にするのも意味があります。CASIOではRENUMでソートされます。

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



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



解答・その5

(ペンネ−ム:巷の夢)

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

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



解答・その6

(ペンネ−ム:三角定規)

(問1) 11回 ( 210−1<2005≦211−1 より,説明は下で)
(問2) 983番目から1023番目
    (コメント:1つずれているかな? by Junko)

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

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

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

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




解答・その7

(ペンネ−ム:夜ふかしのつらいおじさん)

答は、(問1)11回、(問2)982番から1024番です。

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

箱が1個のときは、1回です。
箱が2個のときは、2回です。
箱が3個のときも、2回です。(初めに2番の箱を開けます)
箱が4個のときは、3回です。(初めに2番か3番の箱を開けます。仮に2番の 箱を開けたとすると、右には2個の箱があるので2個の場合を参照します)
箱が5個のときも、3回です。(初めに3番の箱を開けます)
箱が6個のときも、3回です。(初めに3番か4番の箱を開けます。仮に3番の 箱をあけたとすると、右には3個の箱があるので3個の場合を参照します)
箱が7個のときも、3回です。(初めに4番の箱を開けます)
箱が8個のときは、4回です。(初めに4番か5番の箱を開けます。仮に4番の 箱を開けたとすると、右には4個の箱があるので4個の場合を参照します)
・・・・

箱が1個のときは、1回。
箱が2,3個のときは、2回。
箱が4,5,6,7個のときは、3回。
箱が8,9,10,11,12,13,14,15個のときは、4回。
・・・・

開ける回数がk回のとき、最大の箱の個数は2k−1個です。
1回のときは、1個です。つまり、21−1です。
2回のときは、3個です。これは、中央の1個と、その両側に1回のときの1個 ずつです。つまり、

   2×1+1=2+1=(2−1)(2+1)=22−1です。

3回のときは、7個です。これは、中央の1個とその両側に2回のときの3個ず つです。つまり、

   2×(2×1+1)+1=22+2+1 =(2−1)(22+2+1)=23−1です。

4回のときは、15個です。これは、中央の1個とその両側に3回のときの7個 ずつです。つまり、

   2×(2×(2×1+1)+1)+1=23+22+2+1 =(2−1)(23+22+2+1)=24−1です。

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

さて、

   2005=1024+512+256+128+64+16+4+1 =210+29+28+27+26+24+22+1

なので、210<2005<211−1となり、(問1)は11回です。

ところで、k=10回のときの箱の最大の個数は210−1=1023です。
だから、1回目は左に1023個あるようにするか、右側に1023個あるよう にすればよいのです。
つまり、左に1023個のときは1024番目、右に1023個のときは、
2005−1023=982番目の箱を開ければ良いのです。
つまり、(問2)は、982番目から1024番目の範囲なら良いことになりま す。



解答・その8

(ペンネ−ム:FIVEILAND)

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

考え方

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

    210<2005≦211

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

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

    2005−(210-1)=982、210=1024





解答・その9

(ペンネ−ム:なか)

2005が目に止まったので考えてみました。
バイナリーサーチ(二分探索)の問題ですね。

・箱が1個の場合は1回で当たる。
・箱が3個の場合は最初に真ん中を開ければ、最悪でも2回で当たる。
・箱が7個の場合は最初に真ん中を開ければ、外れても候補は3個に絞られるので、最悪でも3回で当たる。
・一般に箱が2−1個の場合は最悪でもn回で当てられる。
・このようにして箱が1023個なら10回で当てられる。
・2005−1023=982なので982を開けるととぎりぎり11回で当てられる。
・同様に1024を開けた場合もぎりぎりだいじょうぶ。

答 (問1)11回 (問2)982〜1024




解答・その10

(ペンネ−ム:Toru)

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

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



解答・その11

(ペンネ−ム:やんま)

1.nは箱を開ける回数、lはn回開けて「当たり」を確実に取り出せる箱の最低数、mはn回開けて「当たり」を確実に取り出せる箱の最大数とすれば、次の表の通りとなる。
箱は2005個であるからl=1024とm=2047の中にある。従って最低11個の箱を開ければよい。 範囲は2番目に開ける時、残っている箱が1023個以下であればよいから 2005−1023=982、即ち982番目を開ければ右側に1023個のこることになる。また1024番目の箱をあけると左側に1023個のこることになる。 従って一番はじめに開ける箱の番号は982から1024番の範囲となる。

答え 1.最低11個、 2.982番〜1024番

nlm
111
223
347
4815
51631
63263
764127
8128255
9256511
105121023
1110242047
1220484095

2.nやlなど記号の意味は1.と同じ
任意の箱の数xからnを求めるには

         [ ]はガウスの記号

lは倍々に増えていくので、求める式は l=2n−1
一番はじめに開ける箱の番号のうち小さい方をMin、大きい方をMaxとすると

   Min=x−(lー1)
   Max=l        で求めることができる。

xに2005を代入して計算するとn=11、l=1024
    Min=2005−(1024−1)=982
    Max=1024

答え 1.最低11個、 2.982番〜1024番





解答・その12

(ペンネ−ム:蜘蛛の巣城)

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

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

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

    2≦箱の個数<2n+1   のとき n+1 回の試技が必要

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

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

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



解答・その13

(ペンネ−ム:小学名探偵)

答え (問1) 11個 (問2) 982以上1024以下

どの箱に当たりが入っていたとしても、M個の箱を開けるまでに(M手以内に)、必 ず当たりが引かれる。 (運が悪くても、M回目に開ける箱には当たりが入っている)このMを最小にするよ うな選び方が、最善の選び方ですね。
いま、最小個数をN、最初に開ける箱の番号をxとします。
箱の個数が1の場合、あきらかにN=1,x=1
箱の個数が2の場合、あきらかにN=2,x=1か2
箱の個数が3(=22-1)の場合、最初に真ん中の箱を開けたとき(x=2のとき)の み、N=2になります。
よって、N=1のとき、箱の個数の最大値=1=21 -1です。 いま、N=nのとき、箱の個数の最大値=2n - 1 と仮定すると、 N=n+1のとき、箱の個数の最大値=2n+1 -1 になります。なぜなら、

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

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

    2n-1≦B≦2n - 1

のとき、N=nになることが示されました。
つぎに、箱の個数Bが、2n-1≦B≦2n - 1のとき、すなわち

   B = 2n - s, ただし、1≦s≦2n-1

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

    2n-1 - (s-1)≦x

(左側にある箱の個数と右側にある箱の個数のうち大きい方≧2n-1 なので、B に対するN=n です) 以上から、xの範囲は、

    2n-1 - (s-1)≦x≦2n-1 (xは2n-1以下、連続するs個の整数値を取る)

になります。

(1)箱の個数2005 = 211(=2048) -43 から、N=11個
(2)最初に開ける箱の番号xは、210 - 42=982≦x≦210=1024

箱の個数Bを2進数で書くと、1ならN=1、10か11ならN=2・・・のように なります。
つまり、1が立っている最も大きな桁番号(Bの桁数)がNの値を与えます。 また、

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

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

2005を2進数で表すと、11111010101

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

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

    ○|○|○|○|・・・○|○

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

     次の検索範囲(ワーストケース)/前の検索範囲≧1/2    式(1)

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

     ”|”の個数=”○”の個数−1               式(2)

ここで、”|”を紙が入った箱に置き換えると、本問のモデルになります。
先のモデルにおける最大値=2n は、このモデルでは、式(2)から、

最大値=2n+2n -1=2n+1 -1
になります。このとき、N=n+1です。

N=nに対する、箱の個数の最大値MAXは、次のようにしても示されます。
)(○|○) ”|”は開箱候補、”○”は左右の箱群、( )は検査ユニット
)(○|○)(○|○) ステップ2では、開箱候補数=2
........
開箱候補数を2進数で書くと、s)1,s)10, s),...sn)10...0(n桁)になります。
ここに、開箱候補に含まれる箱の個数は、1か0です。
あるステップnにおける開箱候補に含まれる箱の個数の総和が1以上であり、次のス テップ(n+1)における開箱候補に含まれる箱の個数の総和が0であるとき、検索 はステップnで完了します。以下、検索はステップnで完了するとします。
このモデルでは、遅かれ早かれ、どの箱にも開箱候補のラベルが付けられることにな るので、ステップ1からステップnまでのすべての開箱候補に含まれる箱の個数を数 え上げれば、与えられた箱の総数になります。
各ステップについて、開箱候補に含まれる箱の個数の最大値=開箱候補の個数 であることから、N=nに対するMAXは、

MAX=s)からs)まですべての開箱候補の総和
=1+10+100,...,10...0(n桁)=11...1(n桁)





正解者

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





まとめ

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





E-mail top