鳩ノ巣原理

質問

１９以下の自然数から、７個の数を適当に選ぶ。この７個の数の中から、いくつかの相異なる数の組を２組選んで、その和を等しくすることができる。

という問題なんですが、鳩ノ巣原理の使い方が分かりませんでした。
どなたが教えてもらえますか？
よろしくお願いします。

回答No.2

proto · ベストアンサー

適当に選んだ7個の数から、いくつかの相異なる数の組を選ぶと2^7-1=127通りの取り方がある。
そのような組で和が最小になるのは(1)を選んだときで和は1,和が最大になるのは(13,14,15,16,17,18,19)を選んだときで和は112。
よって7個の数からいくつかの数を取ると和は1～112の間のどれかになる。
どのような7数を取っても考えられる組は127通りあるから、そのうち和が同じになる取り方が少なくとも２組ある。
この２組の中には重複する数が含まれるかもしれないが、重複する数を組から除けば相異なる数の組を作れる。

お礼

2^7-1=127というのが分からないのですが・・・
7C2と思ったのですが、どうなのでしょうか？

回答No.3

proto

＞7C2と思ったのですが、どうなのでしょうか？
7つの数から2人組を作る場合の数ではないですよ。
7つの数からいくつか(いくつでも)数を取ってきて組を作る場合の数です。

もしa,b,c,d,e,f,gの7数が選ばれたら、いくつかの相異なる数の組は、
(a),(b),(c)のように１個だけ取ってきても良いし、(a,b),(a,c),(c,d)のように二つの数の組や、(a,b,c,d)のように２つより多い組でも構いません。
1人組から7人組までの全ての場合を考えます。

7つの数a,b,c,d,e,f,gからいくつか取って組を作るとすると、
その組にaが入るか入らないかの2通り、さらにbが入るか入らないかの2通り、さらにcが入るか入らないかの2通り、…
で、結局
　　2*2*2*2*2*2*2 = 2^7
通りあるんですが、全ての数が入らないような組は除外されるので、今回考えるのは2^7-1通りです。

お礼

ありがとうございます。分かりました。

回答No.1

koko_u_

>鳩ノ巣原理の使い方が分かりませんでした。
ヒントに鳩の巣原理を使えと書いてあったのですか？？
気にせず問題に取り組めばよい。

お礼

鳩ノ巣原理での練習問題なので、どこかで使用すると思います。