132.石を取り出す問題
1,2,・・・,100の番号のついた100個の箱があり、
それぞれの箱に番号と同じ数の石が入っている。
1回の操作で、この中のいくつかの箱を選び、
それらすべてから同じ数の石を取り出すことができるものとする。
すべての箱を空にするのに最低何回の操作をすればよいですか。
問題の出典
ジュニア数学オリンピック
数学オリンピック財団編
亀書房発行
答えと解説
解答・その1
(ペンネ-ム:オヤジ)
やり方が不明なので、具体的にやりました。
(1)1回目に 51箱から 50個ずつ取り出す。
・{1個},~{49個} ・・2組
・{50個} ・・1組
・「0個」 ・・1箱
(2)2回目に 51箱から 25個ずつ取り出す。
・{1個},~{24個} ・・4組
・{25個} ・・1組
・「0個」 ・・3箱
(3)3回目に 49箱から 13個ずつ取り出す。
・{1個},~{11個} ・・8組
・{12個} ・・5組
・「0個」 ・・7箱
(4)4回目に 53箱から 6個ずつ取り出す。
・{1個},~{5個} ・・16組
・{6個} ・・5組
・「0個」 ・・15箱
(5)5回目に 53箱から 3個ずつ取り出す。
・{1個},~{2個} ・・32組
・{3個} ・・5組
・「0個」 ・・31箱
(6)6回目に 37箱から 2個ずつ取り出す。
・{1個} ・・37箱
・「0個」 ・・63箱
(7)7回目に 37箱から 1個ずつ取り出す。
・「0個」 ・・100箱
∴ 7回
解答・その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個取り出せば、全ての箱は空となる。
解答・その3
(ペンネ-ム:のっこん)
a 個の石が入った箱が2個あっても、a 個の石が入った箱が1個あるのと同じである
この時、箱の数は1個減ったことになる。このように考えて箱の数を減らしていく。
(1)1~2n の時
1回の操作で減らすことができる箱の数の最大はn 個である
(2)1~2n-1 の時
1回の操作で減らすことができる箱の数の最大はn 個である
・1回目
50~100あるいは51~100を選び、すべてから50個取り出す
・・箱の数は50個減る・・1~50が残ったと考えてよい
・2回目
25~50あるいは26~50を選び、すべてから25個取り出す
・・箱の数は25個減る・・1~25が残ったと考えてよい
・3回目
13~25を選び、すべてから13個取り出す
・・箱の数は13個減る・・1~12が残ったと考えてよい
・4回目
6~12あるいは7~12を選び、すべてから6個取り出す
・・箱の数は6個減る・・1~6が残ったと考えてよい
・5回目
3~6あるいは4~6を選び、すべてから3個取り出す
・・箱の数は3個減る・・1~3が残ったと考えてよい
・6回目
2と3を選び、各々から2個取り出す
・・箱の数は2個減る・・1だけが残ったと考えてよい
・7回目
1から1個取り出す
常に箱を最大限減らしてきたから、7回の操作が最小である
・1回目
51~100を選び、すべてから51個取り出してもよい
・2回目
26~50を選び、すべてから26個取り出してもよい
・4回目
7~12を選び、すべてから7個取り出してもよい
・5回目
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つと考えてもよいから、残りの石の数の種類がなるべく少なく
なるように考える。
49箱以下から取り出した場合は、残りの箱を考えれば、残りの種類は51以上と
なる。52箱以上から取リだした場合も、取り出した箱のうち残り0のものを除いて、
残りの種類はやはり51種類以上になる。
50箱、51箱から取り出した時は同様に50種類以上にしかできないが、
1)50個ずつ50-100からあるいは51個ずつ51-100からとると、確かに
1,2,3,------49,1,2,--------50と石の数は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)1個ずつ全てから取り出して終わり
ということで7回
解答・その6
(ペンネ-ム:転位反応)
考え方を示すために、箱の数を10個とし、それぞれの箱の中の石を
下図のように模式的に並べて表すことにする。
題意の操作の回数は、箱に入っている石の数が最も多いものに依存
するので、一回の操作ごとに、その石の数を最少とする取り方を繰り
返せば良いことになる。
を箱から取り出す石とすると、箱の中には最多で5個の石が残る。
図では二つの箱に5個の石が残っている場合を示しているが、どんな
取り出し方をしても、少なくともひとつの箱には5個の石が残る。
ここでは、石が5個入った箱の数は問題とはならない。
以下、同様の考え方で操作を行えばよい。
従って、10個の場合の操作は、最低4回となる。
さて、全く同様な考え方で、箱が100個の場合を考える
箱に入っている最多の石の個数の変化は、
100→50→25→12→6→3→1→0
操作は最低7回となる。
解答・その7
(ペンネ-ム:杖のおじさん)
答え
7回の操作をすれば良いです。
箱の中には5050個の石が入っています。
((1+100)×100)=5050
1~100までの箱の番号を2進法で付番しました。
そうすると100番目の箱は1100110で7桁を必要とします。
箱を選ぶ時は各桁を選び2進法による1と表示されているものを選びその桁の数だけ石を取り出します。
1回目は1桁目が1である50個の箱を選び各箱から1個、合計50個を取り出す。
2回目は2桁目が1である50個の箱を選び各箱から2個、合計100個を取り出す。
3回目は3桁目が1である49個の箱を選び各箱から4個、合計196個を取り出す。
4回目は4桁目が1である48個の箱を選び各箱から8個、合計384個を取り出す。
5回目は5桁目が1である48個の箱を選び各箱から16個、合計768個を取り出す。
6回目は6桁目が1である37個の箱を選び各箱から32個、合計1184個を取り出す。
7桁目は7桁目が1である37個の箱を選び各箱から64個、合計2368個を取り出す。
合計5050個の石を全部取り出すことが出来ました。従って7回の操作で空になる。
解答・その8
(ペンネ-ム:三角定規)
1~100 を2進数表記し,最下位ビットから各ビットに‘1’が立っている箱から
1,2,4,8,16,32,64個ずつ取ればよい。
すなわち,以下の手順で箱を選び石を取れば,7回で取り尽くすことができる。
(1) 石数が奇数個の箱(50個ある)から1個ずつ取り出す。 →
石数はすべて偶数に
(2) 石数を 4 で割ると 2 余る箱(50個ある)から 2 個ずつ取り出す。→
石数はすべて 4 の倍数に
(3) 石数を 8 で割ると 4 余る箱(49個ある)から 4 個ずつ取り出す。→
石数はすべて 8 の倍数に
(4) 石数を 16 で割ると 8 余る箱(48個ある)から 8 個ずつ取り出す。→
石数はすべて 16 の倍数に
(5) 石数を 32 で割ると 16 余る箱(48個ある)から 16 個ずつ取り出す。→
石数は 0,32,64,96 個に
(6) 石数が 32,96 個の箱(37個ある)から 32 個ずつ取り出す。 →
石数は 0,64 個に
(7) 石数が 64 個の箱(37個ある)から 64 個ずつ取り出す。 ← 取り尽くし
上の取り方で,例えば(4)と(5)はそれぞれ 48 個の箱から石を取り出すのだが,
箱が異なるため,これを1回の操作にまとめることはできない。
すなわち,石の取り出しを7回より少なくすることはできない。
[答] 7回
解答・その9
(ペンネ-ム:バルタン星人)
答え:7回
考え方:
100種類を減らしていき、最終的に0種類にすると考える。
種類を減らす最大は、半減+1(奇数の場合、0にできるから)
1回目:奇数番から1個取る。2~100の50種類になる。
これを2×(1~50)と表すと、以下1~50の奇数番から
1(2×1で2個とる)取り、これを繰り返すと
4×(1~25)
8×(1~12)
16×(1~6)
32×(1~3)
64×1
0
となり7回が最低の回数となる。
解答・その10
(ペンネ-ム:夜ふかしのつらいおじさん)
この問題は、直角二等辺三角形からその三角形に内接する長方形を繰り返して
くり抜く作業と似ています。
直角二等辺三角形に内接する長方形で面積が最大であるのは正方形のときで、
その正方形の面積は、もとの直角三角形の面積の半分です。
右の図で正方形をくり抜いたとき、小さな直角二等辺三角形が残ります。
この二つの直角二等辺三角形は合同で、この二つに同じことを繰り返します。
この作業が無限に続きます。
石の場合には有限回で操作が終わります。
箱の個数が、2n-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個の場合は次のように7回の操作ですべての箱は空になります。
解答・その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
したがって、最小7回。
解答・その14
(ペンネ-ム:庄司)
この問題は、2進法とその和で考えました。
方法;20、21、22……26が書かれた番号の箱からは、
1回の施行で全部の石を取り出すことにし、それ以外の番号の箱からは、上記の数の組み
合わせで全ての石を取り出します。
例えば3番の箱の石は、1番(20)の箱と、2番(21)の箱から……
50番の箱の石は、32番の箱(25)、16番の箱(24)、2番(21)の箱から
石を取り出す間に、箱の中の石を全て取りきることが出来ます。
26<100<27ですので、最低7回の施行で100までの箱から全ての石を取
り出せることになります。
解答・その15
(ペンネ-ム:teki)
答え 7回の操作で可能です。
以前にあった、バイナリリサーチ(二分探索)と同様の考え方ができますね。
箱が2n-1から2n-1までの場合はn回で可能です。
実際のやり方は、箱の個数が奇数の場合は、中央の個数をそれ以上入っている箱
から、偶数の場合は、N/2+1個以上入っている箱から、それぞれ取り出せるだけ
取り出すことを繰り返せば可能です。
で、26≦100≦27-1 なので、100個の箱の場合は、
7回が最短手数となります。
実際にやってみたわけではないですが、多分これでいいと思います。
正解者
バルタン星人 | kiyo | 夜ふかしのつらいおじさん |
T_Tatekawa | teki | のっこん |
こまったコ | Toru | 巷の夢 |
転位反応 | 杖のおじさん | スモークマン |
オヤジ | 三角定規 | 庄司 |
まとめ
100種類の数から、石を取ることで、種類数を半分、半分と減らしていくという
アイディアの解答が多かったですね。
26≦100<27
ですから、
最低7回ということになります。
また、石を取るか、取らないか、2通りの選択肢があるわけですから、
1から100までの数を、2進数で表わし、
桁ごとに、1と表記された数から、その数を取っていくという
考え方もできますね。一番大きい100を2進数で表すと、
100=1100100(2)
と7桁ですから、最低7回必要だということになります。