Question

M

括弧2がよくわかりません
教えてください(鳩の巣原理の問題です)

2.3 次の問に答えよ。
(1) 1, 2, 3 の3つの数の少なくとも1つを用いて作ることのできる数の組は,
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
の7組である。
1, 2, 3, 4, 5, 6, 7 の 7つの数の少なくとも1つを用いて作ることのできる
数の組は何組できるか.
20 の相異なる20個の数から任意に異なる7個の数を取り出す
とき,その7個のうちのいくつかを用いて,含まれる数の合計が等しくなるよ
うな,同じ数を含まない2つの数の組を作ることができることを示せ.
例えば,7個の数が,
{1, 3, 4, 5, 14, 17, 20}
のとき,3+20=23, 4+5+14=23 より,
{3, 20), {4, 5, 14}
のような,含まれる数の合計が等しく,同じ数を含まない2つの数の組を作る
ことができる。
スて
に

Answer 1

✨ ベストアンサー ✨

暇つぶし

復習したり調べたりしてなんとかって感じなんですが，
いかがでしょうか．

合計が同じ「同じ数を含むことを許容して」二つの数の組(※)を考えることにします．
二つの数の組から同じ数を取り除けば，合計を等しくしたままに
合計が同じ「同じ数を含まない」二つの数の組を構成できます．

鳩の巣は「含まれる数」の合計で構成します．
※のような組を考えているので，合計値の範囲は
最小 = 1
最大 = Σ(k= 0 ~ 6){20 - k} = 119
となり，鳩の巣の数は 119 - 1 + 1 = 119 です．

7個の数から少なくともいずれか一つを含む数の組は(1)の答えから
2^7 - 1 = 127
個あります．

これらの数の組を鳩の巣に分配すると，
⌈127/119⌉ = 2
より少なくとも合計値が同じ数の組が二つ存在することがわかります．

M

ありがとうございます！
わかりやすくて助かりました！