3つの集合すべてに属する人数の最小

方針

解答

⓪ 発想 — どう考え始めるか。 最小値の問題は、2本立てで考える。「下から押さえる不等式」と、「その値を達成する実例」だ。

押さえには補集合(ド・モルガン)が効く。3つすべてを満たさない者は、「A でない」「B でない」「C でない」のどれかに入る。だからその人数は、各補集合の人数の和 $20+25+35=80$ を超えない。よって3つとも満たす者は、少なくとも $100-80=20$ 人。

達成には、3つの補集合(計80人)を互いに重ならないように配置した実例を作ればよい。$80\le 100$ だから可能だ。

① 下から押さえる。 補集合の人数は $|\overline{A}|=20,|\overline{B}|=25,|\overline{C}|=35$。3つすべてを満たさない者の集合は $\overline{A}\cup \overline{B}\cup \overline{C}$ で、その人数は

$$|\overline{A}\cup \overline{B}\cup \overline{C}|\le 20+25+35=80$$

よって、3つすべてを満たす者は

$$100-|\overline{A}\cup \overline{B}\cup \overline{C}|\ge 100-80=20\text{人}$$

② 20人が達成できることを示す。 100人を次のように分ける。「A だけ満たさない」20人。「B だけ満たさない」25人。「C だけ満たさない」35人。「3つとも満たす」20人($20+25+35+20=100$ ✓)。

このとき A を満たすのは $100-20=80$ 人、B は $100-25=75$ 人、C は $100-35=65$ 人。条件をすべて満たし、3つとも満たす者はちょうど20人だ。

③ 結論。 最小値は $20$ 人。

まとめ: 「すべて」の最小は、補集合の「少なくとも1つ」に裏返して和で押さえる。そして達成例の構成(補集合たちを互いに素に敷き詰める)までが答案だ。補集合の合計が全体を超えるかどうか($80\le 100$)が、最小値が正になるか0で止まるかの分かれ目になっている。

別解

表側から、2段階で絞る(補集合を使わないルート)。 「A かつ B」の人数から順に押さえていく方法もある。

まず2つ。A が80人、B が75人。合わせて155人ぶんの「所属」が、100人の中に詰め込まれている。あふれた $155-100=55$ 人ぶんは重なりだ:

$$|A\cap B|\ge 80+75-100=55$$

次に「A かつ B」(55人以上)と C(65人)で同じことをする:

$$|A\cap B\cap C|\ge 55+65-100=20$$

2段階の絞り込みで、同じ下界20人に着く。

どちらのルートも正体は同じ勘定だが、性格は少し違う。補集合ルートは1行で全体を押さえ、こちらは「2つずつ」の直感(あふれた分は重なる)を積み重ねる。あふれの感覚がつかみやすい人は、この段階式が手になじむはずだ。