ホーム >> 組合せ >> $6$ 種類のカード
hide or visible

問題の説明

説明のために$6$種類のカードをそれぞれ$A,B,C,D,E,F$としましょう.合計$120$枚のカードを何人かの子供に分け与えます.このとき,$1$人の子供に対して同じ種類のカードを$2$枚以上は配りません.

問題文最後の条件は,$2$人の子供のカードを合わせて$6$種類すべてが揃うことはないということです.例えば,$A,B,C$の$3$枚を配られた子供と$D,E,F$の$3$枚を配られた子供がいることはありえません.また,$A,B,C,D,E,F$のすべてを$1$枚ずつ配られた子供がいることも当然ありえません.さらに,$5$種類のカードを配られた子供もいないことがわかります.

簡単な実験

いきなり$n$の最小値を見出すのは難しいので,まずは簡単に実験をしてみましょう.カードは$120$枚あるので,例えば$120$人の子供がいたらどうでしょうか.このときは$1$人に$1$枚ずつ配れば条件を容易に満たします.では半分の$60$人ではどうでしょうか.$1$人に$2$枚ずつ配ったとしましょう.すると,このときも条件を満たします.なぜならどの$2$人の子供のカードを合わせてもその枚数は$4$枚なので,$6$種類すべてが揃うことはないからです.

では,問題の条件を満たすように$1$人に$3$枚ずつ配ることは可能でしょうか.

$n=40$のとき条件を満たす配り方が存在すること

以下の表を見てください.

type1. $A,B,C$
type2. $A,B,D$
type3. $A,C,E$
type4. $A,D,F$
type5. $A,E,F$
type6. $B,C,F$
type7. $B,D,E$
type8. $B,E,F$
type9. $C,D,E$
type10. $C,D,F$

各typeの配り方を$4$人ずつ計$40$人の子供に配ります.このようにすると各種類のカードは上の表で$5$回ずつ表れているので,$20$枚すべてが配られます.また,どの$2$つのtypeのカードを合わせても$6$種類のカードすべてが揃うことはありません.したがってこの配り方は問題文の条件を満たします.よって,$n=40$が実現することがわかりました.

$n=40$が最小であることの証明

さて,$n=40$が最小の値であることを示します.
もし,どの子供にも$3$種類以下しか配らないとすると,カードは全部で$120$枚あるので子供の人数は必ず$40$人以上になります.また,$5$種類または$6$種類のカードが配られる子供は存在しません.$4$種類のカードが配られた子供が存在したとしましょう.仮にそれらを$A,B,C,D$とします.このとき問題の条件から,$E,F$の両方を配られた子供は存在しません.したがって,$E$を配られた子供が$20$人,$F$を配られた子供が$20$人存在します.$A,B,C,D$を配られた子供と合わせると子供の人数は$41$人以上です.以上より,$n=40$が最小値であることが示せます.


$10$typeの分け方は他にも存在します.