鳩ノ巣理論について （数学パズル）

質問

鳩ノ巣問題の質問です。　１．キャンディーが２０個あります。　２．入れ物が１１個あり、どの入れ物にも１個以上キャンディーを入れます。　３．　このとき、どのような入れ方をしても、入れ物１１個を２つの組に分けて、どちらにもキャンディーが１０個ずつになるような入れ物の分け方があることを証明したいです。　宜しくお願い致します。

回答No.5

MijumaruGT

問題が出されてからだいぶ時間がたっているみたいですが、
わかったような気がするので回答してみます。

条件に合う方法でキャンディーを各入れ物に分けたとして、
それを多い順に並べてみます。
簡単のため、各入れ物の中のキャンディーの個数を数列で表します。
たとえば、各箱に８個、３個、１個、１個、・・・（以下すべて１個）のとき、
[8,3],9のように書きます。
[...]の中は各箱の中のキャンディの個数、その後の数字は中身が１個の箱の数です。
説明のため記号を使って
[n(1),n(2),...],k
のようにあらわすことにします。

すると、n(1)>n(2)>...となります。
また、k>=n(1)です。　※１

まず[...]の部分を２つに分けます。
うまく分けると、２つに分けたときのキャンディの個数の差をn(1)以下にすることができます。　※２

１個の箱はk>=n(1)あるので、
それらをうまく割り振ることで、２つに分けたときのキャンディの個数を等しくする
（個数の差を埋める）ことができます。

※１）ここが塾の先生が言うところの鳩ノ巣理論と思われます。
まず最低キャンディーをひとつずつ各箱に割り当てなくてはならないので、
問題は残り９個のキャンディの割り当て方ということになります。
そのうちのn(1)-1個が一つ目の箱に割り当てられると、残りは10-n(1)となり、
それを残りの10個の箱に割り当てなくてはなりません。
10-n(1)個のキャンディを10個の箱に割り当てようとすると、少なくともn(1)個の箱の割り当ては０になります。
つまり、少なくともn(1)個の箱のキャンディは１個ということになります。

※２）
たとえば、A,Bに分けるときに、
まずn(1)をAに割り当てます。
n(1)を超えるまでn(2),n(3),...を割り当てます。
超えたら次の箱からAに割り当てます。
こうやって分けた二つのグループはn(1)を超えません。

回答No.4

paso_com

１．キャンディーを入れた籠を一列に並べます。
２．端から1番目、２番目…１１番目までの籠に入ったキャンディーの数を合計します。
　　どの籠にも１個以上入れているので以下の様になります。
　　　　１個≦合計１＝籠１
　　　　　　　合計２＝籠１＋籠２
　　　　　　　合計３＝籠１＋籠２＋籠３
　　　　　　　　：　　　　：
　　　１９個≧合計１０＝籠１＋籠２＋籠３…＋籠１０
　　　２０個＝合計１１＝籠１＋籠２＋籠３…＋籠１０＋籠１１
３．さて合計１から合計１０の中には
　　（１）１０で割り切れるものがある。
　　（２）１０で割った余りが等しい組がある。
　　のどちらかです。
４．（１）の場合、１０で割り切れるものを合計ｎとすると
　　１個≦合計ｎ≦１９個ですので、合計ｎ＝１０個となります。
５．（２）の場合、余りが等しい組を、（合計ｍ、合計ｎ）（ｍ＞ｎ）とすると、
　　合計ｍの籠から合計ｎの籠を取り去れば、残りの籠のキャンデー数の合計は１０の倍数になり、４．と同じ理由で１０個になります。
６．以上によって、
　　１１個の籠を２組に分けて籠の中のキャンディーの合計を１０個ずつにすることができます。

以上

回答No.3

noname#235817

9個の赤いキャンディーは、入れ物にどのような入れ方をしてもいい、つまり、10個ずつになるように振り分ければいいということです。
なので、
>赤いキャンディーを(3,6)で分けたとき、ちょうど白いキャンディーが入った入れ物が(7,4)で分けられているとは限らない。
ではなく、
「白いキャンディーが入った入れ物を(7,4)で分けたとき、赤いキャンディーを(3,6)で振り分ければよい」、ということです。

問題文は、このような分け方が必ず存在することを示せ、なので、
10個ずつとなる場合を全て書き出すのも手ですが、一般的には

「1．偶数個のキャンディーがあります。2．それより小さい奇数個の入れ物があり、・・・」
という問題で考えますと、赤いキャンディーの数は必ず奇数個になります。入れ物の数も奇数です。
したがって、奇数＋奇数＝偶数（つまり2で割り切れる）
ということを証明すればいいと思います。もちろんこの場合は、入れ物の分け方によっては同じ数ずつにキャンディーが分けられない場合もあります。

※最初の回答に書いた、2n+(2n+2)=…というのは、たまたまキャンディーが20個、入れ物が11個で、赤いキャンディーが9個という状況で考えた場合です。

お礼

どのようなわけ方をしても（この場合は赤いキャンディ９個を、１１個の入れ物にどのようなわけ方をしても）、１０個ずつに分けられることと、「白いキャンディーが入った入れ物を(7,4)で分けたとき、赤いキャンディーを(3,6)で振り分ければよい」、つまり分けられる分け方が存在する、ということが同値だというところがよく理解できません。　申し訳ございませんが、
ここを再度ご教示願えませんでしょうか。　宜しくお願い申し上げます。

回答No.2

noname#235817

入れ物は11個なので、これを二組に分ける分け方は
2+9,3+8, 7+4
というように、必ず「偶数と奇数のペア」となります。

一方、どの入れ物にも必ず一つはキャンディーが入るので、先にキャンディーを一つずつ入れ物に入れると、残りのキャンディーは9個となります。

11=1+10, 2+9, 3+8, 4+7, 5+6 (0+11は×）
10=・・・
9=0+9, 1+8, 2+7, 3+6, 4+5

ここで、この問題は次の問題に書き換えることができます。
問題「ある数nと、その数に2を加えた数n+2を足すと、その数は必ず2で割り切れることを証明せよ。」

したがって、n+(n+2)=2n+2=2(n+1)
より、必ず2で割り切れる。

お礼

ありがとうございます。
どうにも解決の端緒すらつかめずに悩んでおりました。

中学一年の娘が塾で出されたものですが、全ての場合分けをすれば、それほど場合の数が多くないために証明できるのですが、先生が
鳩ノ巣論法で一発でできるとおっしゃっていたようで、なんらか
エレガントな解答があるのだろうと思いながらも、手が付けられずに
おりました。

回答をいただいた文章ですが、上から４行まではわかります。

ここで、
２０個のキャンディを白いキャンディ１１個と赤いキャンディ９個に分けるとして、白いキャンディは先に一個ずつ入れ物に入れておくこととします。（後から９個の赤いキャンディを好きなように１１個の入れものに入れる。）

６行目は、この場合、入れ物を数個ずつ二人に分けると、白いキュンディが１個と１０個、あるいは２個と８個に分かれるということをおっしゃっているのでしょうか？

また、１０＝・・・とは、何を指しているのでしょうか？

また、その下の行は、赤いキャンディ９個が適当に入れ物に入っており、入れ物を何個かずつ２人に分けるとすると、赤いキャンディは０個と９個、あるいは１個と８個・・・に分かれることを意味しておりますでしょうか？

そうなると、たとえば赤いキャンディが２個と７個に分かれたとすると、そのわけ方のときに、白いキャンディが都合よく、８個と３個に分かれていれば二人に１０個と１０個に分けられますが、必ずそうなると言い切れることがよく理解できません。

追加でご教示頂ければ幸いです。

宜しくお願い申し上げます。

回答No.1

yaemon_2006

飴を 1 個づつ箱に入れると、残りは、 9 個。

足して 9 になる 0 以上の整数の組み合わせは、
(0, 9) (1, 8) (2, 7) (3, 6) (4, 5) の 5 通り。

足して 11 になる 1 以上の整数の組み合わせは、
(10, 1) (9, 2) (8, 3) (7, 4) (6, 5) の 5 通り。
それぞれの 10 個との差は、
(0, 9) (1, 8) (2, 7) (3, 6) (4, 5) の 5 通り。

お礼

最初の方に対する回答を真似すれば、赤いキャンディが０個と９個、や、
１個と８個・・・・に分かれて、白いキャンディが、１０個と１個、９個と２個・・・に分けられることを意味しておりますか？

たとえば赤いキャンディが３個と６個に分かれるように入れ物を２つに分けた時に、白いキャンディが７個と４個に分かれているように、うまく入れ物が分けられるのかが心配です。

宜しくご教示ください。