問題132

１３２．石を取り出す問題

１，２，・・・，１００の番号のついた１００個の箱があり、それぞれの箱に番号と同じ数の石が入っている。１回の操作で、この中のいくつかの箱を選び、それらすべてから同じ数の石を取り出すことができるものとする。すべての箱を空にするのに最低何回の操作をすればよいですか。

問題の出典

ジュニア数学オリンピック
数学オリンピック財団編
亀書房発行

答えと解説

解答・その1

（ペンネ－ム：オヤジ）

　やり方が不明なので、具体的にやりました。

（１）１回目に　５１箱から　５０個ずつ取り出す。
・｛１個｝，～｛４９個｝　・・２組
・｛５０個｝　　　　　　　・・１組
・「０個」　　　　　　　　・・１箱

（２）２回目に　５１箱から　２５個ずつ取り出す。
・｛１個｝，～｛２４個｝　・・４組
・｛２５個｝　　　　　　　・・１組
・「０個」　　　　　　　　・・３箱

（３）３回目に　４９箱から　１３個ずつ取り出す。
・｛１個｝，～｛１１個｝　・・８組
・｛１２個｝　　　　　　・・５組
・「０個」　　　　　　　・・７箱

（４）４回目に　５３箱から　６個ずつ取り出す。
・｛１個｝，～｛５個｝　・・１６組
　・｛６個｝　　　　　　・・５組
・「０個」　　　　　　　・・１５箱

（５）５回目に　５３箱から　３個ずつ取り出す。
・｛１個｝，～｛２個｝　・・３２組
・｛３個｝　　　　　　・・５組
・「０個」　　　　　　・・３１箱

（６）６回目に　３７箱から　２個ずつ取り出す。
・｛１個｝　　　　　　・・３７箱
・「０個」　　　　　　・・６３箱

（７）７回目に　３７箱から　１個ずつ取り出す。
・「０個」　　　　　　・・１００箱

　　　∴　７回

解答・その2

（ペンネ－ム：巷の夢）

まず1～100までの箱を2グループに分ける。即ち、1～50と51～100とする。そして後者のグループから各々50個づつ取り出す。すると後者のグループも1～50となる。
次に1～50までの箱を2グループに分ける。即ち、1～25と26～50とする。そして後者のグループから各々25個づつ取り出す。すると後者のグループも1～25となる。
更に1～25までの箱を2グループに分ける。即ち、1～12と13～25とする。そして後者のグループから各々13個づつ取り出す。すると後者のグループは0～12となる。
これ以降は上記と同様な操作を繰り返す。即ち、0～6と7～12そして後者のグループから各々6個づつ取り出す。すると後者のグループは1～6となる。
0～6の箱を0～3と4～6に分け、後者のグループから各々3個づつ取り出す。すると後者のグループは1～3となる。
そこで、0～3の箱を0～1と2～3に分け、後者のグループから各々2個づつ取り出す。すると後者のグループは0～1となる。
ここで全ての箱の中身は0ないし1個となったので、1個取り出せば、全ての箱は空となる。

これまでの操作回数である①～⑦までの7回が求める回数である。

解答・その3

（ペンネ－ム：のっこん）

a 個の石が入った箱が2個あっても、a 個の石が入った箱が1個あるのと同じであるこの時、箱の数は1個減ったことになる。このように考えて箱の数を減らしていく。

(1)1～2n の時
　１回の操作で減らすことができる箱の数の最大はn 個である
(2)1～2n-1 の時　
　１回の操作で減らすことができる箱の数の最大はn 個である

・１回目
　　50～100あるいは51～100を選び、すべてから50個取り出す
　　・・箱の数は50個減る・・1～50が残ったと考えてよい
・２回目
　　25～50あるいは26～50を選び、すべてから25個取り出す
　　・・箱の数は25個減る・・1～25が残ったと考えてよい
・３回目
　　13～25を選び、すべてから13個取り出す
　　・・箱の数は13個減る・・1～12が残ったと考えてよい
・４回目
　　6～12あるいは7～12を選び、すべてから6個取り出す
　　・・箱の数は6個減る・・1～6が残ったと考えてよい
・５回目
　　3～6あるいは4～6を選び、すべてから3個取り出す
　　・・箱の数は3個減る・・1～3が残ったと考えてよい
・６回目
　　2と3を選び、各々から2個取り出す
　　・・箱の数は2個減る・・1だけが残ったと考えてよい
・７回目
　　1から1個取り出す

常に箱を最大限減らしてきたから、７回の操作が最小である

・１回目
　　51～100を選び、すべてから51個取り出してもよい
・２回目
　　26～50を選び、すべてから26個取り出してもよい
・４回目
　　7～12を選び、すべてから7個取り出してもよい
・５回目
　　4～6を選び、すべてから4個取り出してもよい

解答・その4

（ペンネ－ム：こまったコ）

一度にできるだけ多くの箱から同じ数を取り出せるとよい。
根拠はないが最大100個の半分の50個をまず取り出す。

1回目・・・50個取り出す。
1～49の箱からは取り出せないのでそのまま。
50～100の箱からはそれぞれ50個ずつ取り出す。
それぞれ　0, 1, 2, ...., 49, 50個残る。
これをまとめると
1～49個残っている箱がそれぞれ2箱、50個残っている箱が1箱。

2回目・・・25個取り出す。
1～24個残っている箱からは取り出せないのでそのまま。
25～50個残っている箱からはそれぞれ25個ずつ取り出す。
それぞれ　0, 1, 2, ...., 24, 25個残る。
これをまとめると
1～24個残っている箱がそれぞれ4箱、25個残っている箱が1箱。

3回目・・・13個取り出す。
1～12個残っている箱からは取り出せないのでそのまま。
13～25個残っている箱からはそれぞれ13個ずつ取り出す。
それぞれ　0, 1, 2, ...., 11, 12個残る。
これをまとめると
1～11個残っている箱がそれぞれ8箱、12個残っている箱が5箱。

4回目・・・6個取り出す。
1～5個残っている箱からは取り出せないのでそのまま。
6～12個残っている箱からはそれぞれ6個ずつ取り出す。
それぞれ　0, 1, 2,..5, 6個残る。
これをまとめると
1～5個残っている箱がそれぞれ16箱、6個残っている箱が5箱。

5回目・・・3個取り出す。
1～2個残っている箱からは取り出せないのでそのまま。
3～6個残っている箱からはそれぞれ3個ずつ取り出す。
それぞれ　0, 1, 2, 3個残る。
これをまとめると
1～2個残っている箱がそれぞれ32箱、3個残っている箱が5箱。

6回目・・・2個取り出す。
1個残っている箱からは取り出せないのでそのまま。
2～3個残っている箱からはそれぞれ3個ずつ取り出す。
それぞれ　0, 1個残る。
これをまとめると
1個残っている箱が37箱。

7回目・・・すべての箱から1個ずつ取り出す。
これですべての箱の玉がなくなる。

以上より、7回。

解答・その5

（ペンネ－ム：Toru）

求める数をf(100)とする
　石の数が同じ箱は１つと考えてもよいから、残りの石の数の種類がなるべく少なくなるように考える。
　４９箱以下から取り出した場合は、残りの箱を考えれば、残りの種類は５１以上となる。５２箱以上から取リだした場合も、取り出した箱のうち残り０のものを除いて、残りの種類はやはり５１種類以上になる。
　５０箱、５１箱から取り出した時は同様に５０種類以上にしかできないが、

1)50個ずつ50-100からあるいは51個ずつ51-100からとると、確かに 1,2,3,------49,1,2,--------50と石の数は５０種類となる。
　この取り方が最善でのこりは、f(50)。

　　以下同様に
2)25個ずつ25-50からあるいは26個ずつ26-50からとりだして　

のこりf(25)
3)13個ずつ13-25から取り出して　
のこりf(12)
4)6個ずつ6-12あるいは7個ずつ7-12から取り出して
のこりf(6)
5)3個ずつ3-6あるいは4個ずつ4-6から取り出して
のこりf(3)
6)2個ずつ2-3から取り出して
のこりf(1)
7)１個ずつ全てから取り出して終わり
ということで７回

解答・その6

（ペンネ－ム：転位反応）

考え方を示すために、箱の数を１０個とし、それぞれの箱の中の石を下図のように模式的に並べて表すことにする。題意の操作の回数は、箱に入っている石の数が最も多いものに依存するので、一回の操作ごとに、その石の数を最少とする取り方を繰り返せば良いことになる。
　を箱から取り出す石とすると、箱の中には最多で５個の石が残る。
図では二つの箱に５個の石が残っている場合を示しているが、どんな取り出し方をしても、少なくともひとつの箱には５個の石が残る。ここでは、石が５個入った箱の数は問題とはならない。

以下、同様の考え方で操作を行えばよい。

従って、１０個の場合の操作は、最低４回となる。

さて、全く同様な考え方で、箱が１００個の場合を考える
箱に入っている最多の石の個数の変化は、

　　　100→50→25→12→6→3→1→0

操作は最低７回となる。

解答・その7

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

答え
７回の操作をすれば良いです。
箱の中には５０５０個の石が入っています。

　　　（（１＋１００）×１００）＝５０５０

１～１００までの箱の番号を２進法で付番しました。
そうすると１００番目の箱は１１００１１０で７桁を必要とします。
箱を選ぶ時は各桁を選び２進法による１と表示されているものを選びその桁の数だけ石を取り出します。

１回目は１桁目が１である５０個の箱を選び各箱から１個、合計５０個を取り出す。
２回目は２桁目が１である５０個の箱を選び各箱から２個、合計１００個を取り出す。
３回目は３桁目が１である４９個の箱を選び各箱から４個、合計１９６個を取り出す。
４回目は４桁目が１である４８個の箱を選び各箱から８個、合計３８４個を取り出す。
５回目は５桁目が１である４８個の箱を選び各箱から１６個、合計７６８個を取り出す。
６回目は６桁目が１である３７個の箱を選び各箱から３２個、合計１１８４個を取り出す。
７桁目は７桁目が１である３７個の箱を選び各箱から６４個、合計２３６８個を取り出す。

合計５０５０個の石を全部取り出すことが出来ました。従って７回の操作で空になる。

解答・その8

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

１～１００を２進数表記し，最下位ビットから各ビットに‘１’が立っている箱から１，２，４，８，１６，３２，６４個ずつ取ればよい。すなわち，以下の手順で箱を選び石を取れば，７回で取り尽くすことができる。

(1) 石数が奇数個の箱（50個ある）から１個ずつ取り出す。　　　　　　　　　→ 石数はすべて偶数に
(2) 石数を４で割ると２余る箱（50個ある）から２個ずつ取り出す。→ 石数はすべて４の倍数に
(3) 石数を８で割ると４余る箱（49個ある）から４個ずつ取り出す。→ 石数はすべて８の倍数に
(4) 石数を１６で割ると８余る箱（48個ある）から８個ずつ取り出す。→ 石数はすべて１６の倍数に
(5) 石数を３２で割ると１６余る箱（48個ある）から１６個ずつ取り出す。→ 石数は０，３２，６４，９６個に
(6) 石数が３２，９６個の箱（37個ある）から３２個ずつ取り出す。　　　　→ 石数は０，６４個に
(7) 石数が６４個の箱（37個ある）から６４個ずつ取り出す。　　← 取り尽くし

上の取り方で，例えば(4)と(5)はそれぞれ４８個の箱から石を取り出すのだが，箱が異なるため，これを１回の操作にまとめることはできない。すなわち，石の取り出しを７回より少なくすることはできない。

［答］　７回

解答・その9

（ペンネ－ム：バルタン星人）

答え：７回

考え方：
１００種類を減らしていき、最終的に０種類にすると考える。種類を減らす最大は、半減＋１（奇数の場合、０にできるから）
１回目：奇数番から１個取る。２～１００の５０種類になる。
これを２×（１～５０）と表すと、以下１～５０の奇数番から１（２×１で２個とる）取り、これを繰り返すと
　４×（１～２５）
　８×（１～１２）
　１６×（１～６）
　３２×（１～３）
　６４×１
　０
となり７回が最低の回数となる。

解答・その10

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

この問題は、直角二等辺三角形からその三角形に内接する長方形を繰り返してくり抜く作業と似ています。
直角二等辺三角形に内接する長方形で面積が最大であるのは正方形のときで、その正方形の面積は、もとの直角三角形の面積の半分です。
右の図で正方形をくり抜いたとき、小さな直角二等辺三角形が残ります。この二つの直角二等辺三角形は合同で、この二つに同じことを繰り返します。この作業が無限に続きます。
石の場合には有限回で操作が終わります。
箱の個数が、2ⁿ-1の場合は典型的にうまくいきます。
例えば、7個（n=3)の場合は

　1回目、｛4，5，6，7｝の箱から4個の石を取る
　2回目、｛2，3，6，7｝の箱から2個の石を取る
　3回目、｛1，3，5，7｝の箱から1個の石を取る
のように、3回の操作で空にできます。この操作数が最低といえるのは、とる石の個数が最大と分かっているからです。この様子を箱に残る石の個数で

と表すことにします。

箱の個数を変えてみます。例えば8個としてみます。

　1回目、｛5，6，7，8｝の箱から5個の石を取る
　2回目、｛3，4，8｝の箱から3個の石を取る
　3回目、｛2，6｝のはこから2個の石を取る
　4回目、｛1，4，5，7，8｝の箱から1個の石を取る

1回目めに｛4，5，6，7，8｝の箱から4個の石を取っても例1と同じ状態になる

　1回目、｛5，6，7，8｝の箱から4個の石を取る
　2回目、｛3，4，7，8｝の箱から2個の石を取る
　3回目、｛2，4，6，8｝の箱から1個の石を取る
　4回目、全部の箱から1個の石を取る
のように、半数前後の石を取っていけば、操作数に違いはないようです。
さて、100個の場合は次のように７回の操作ですべての箱は空になります。

解答・その11

（ペンネ－ム：スモークマン）

逆から考えると、、、1 は残る。
その前に2は残ってるので、2を取ることを考える。
1+2=3
2, が残っていたことになる。
4は取られていないといけない。
1+4=5
1+2+4=7
2+4=6
は残っていたことになる。
8は取られていないといけない。
以下同様に、、、
16,32,64が取られていないといけない。
つまり、100から、64,32,16,8,4,2,1 を取れば空になる。計7回必要・・・かな？^^

解答・その12

（ペンネ－ム：T_Tatekawa）

石の数を 2 進数で表して考えてみます．

2*2 = 4
2*2*2 = 8
2*2*2*2 = 16
2*2*2*2*2 = 32
2*2*2*2*2*2 = 64
2*2*2*2*2*2*2 = 128 > 100

なので，100 は 2 の 7 乗より小さいです．
例えば 100 を 2 進数で表すと，「1100100」になります．
他の数字も 2 進数で表し，選んだ桁が "1" になったときに石を取り出す操作をしていけばいいのではないでしょうか．

具体的な操作は以下の通りで，7 回です．
1. 番号が64以上の箱を選んで，石を64個ずつ取り出す．
2. 中に石が32個以上残っている箱から，32個ずつ石を取り出す．
3. 中に石が16個以上残っている箱から，16個ずつ石を取り出す．
4. 中に石が8個以上残っている箱から，8個ずつ石を取り出す．
5. 中に石が4個以上残っている箱から，4個ずつ石を取り出す．
6. 中に石が2個以上残っている箱から，2個ずつ石を取り出す．
7. 中に石が残っている箱から，1個ずつ石を取り出す．

解答・その13

（ペンネ－ム：kiyo）

解答

　　　100＜64+32+16+8+4+2+1
　　　(1+100)*100/2=5050=64*37+32*37+16*48+8*48+4*49+2*50+1*50

したがって、最小７回。

解答・その14

（ペンネ－ム：庄司）

この問題は、2進法とその和で考えました。

方法；2⁰、2¹、2²……2⁶が書かれた番号の箱からは、 1回の施行で全部の石を取り出すことにし、それ以外の番号の箱からは、上記の数の組み合わせで全ての石を取り出します。

例えば3番の箱の石は、1番(2⁰)の箱と、2番(2¹)の箱から…… 50番の箱の石は、32番の箱(2⁵)、16番の箱(2⁴)、2番(2¹)の箱から石を取り出す間に、箱の中の石を全て取りきることが出来ます。

2⁶＜100＜2⁷ですので、最低7回の施行で100までの箱から全ての石を取り出せることになります。

解答・その15

（ペンネ－ム：teki）

答え　　７回の操作で可能です。
以前にあった、バイナリリサーチ（二分探索）と同様の考え方ができますね。
箱が２^ｎ－１から２^ｎ－１までの場合はｎ回で可能です。
実際のやり方は、箱の個数が奇数の場合は、中央の個数をそれ以上入っている箱から、偶数の場合は、N/２＋１個以上入っている箱から、それぞれ取り出せるだけ取り出すことを繰り返せば可能です。
で、２^６≦１００≦２^７－１　なので、１００個の箱の場合は、７回が最短手数となります。実際にやってみたわけではないですが、多分これでいいと思います。

正解者

バルタン星人 kiyo 夜ふかしのつらいおじさん
T_Tatekawa teki のっこん
こまったコ Toru 巷の夢
転位反応杖のおじさんスモークマン
オヤジ三角定規庄司

まとめ

１００種類の数から、石を取ることで、種類数を半分、半分と減らしていくというアイディアの解答が多かったですね。
　　　２^６≦１００＜２^７
ですから、最低７回ということになります。
また、石を取るか、取らないか、２通りの選択肢があるわけですから、１から１００までの数を、２進数で表わし、桁ごとに、１と表記された数から、その数を取っていくという考え方もできますね。一番大きい１００を２進数で表すと、
　　　１００＝1100100(2)
と７桁ですから、最低７回必要だということになります。

Challenge!