ある商店街に10軒の食品関係の商店があります。この中で、パンを売っている商店は6軒、ソフトクリームを売っている商店は8軒、清涼飲料を売っている商店は9軒です。どの商店も、パン、ソフトクリーム、清涼飲料のいずれか1つは売っています。このとき、パンもソフトクリームも清涼飲料も売っている商店は少なくとも何軒あるか求める問題です。

1. 問題の内容

ある商店街に10軒の食品関係の商店があります。この中で、パンを売っている商店は6軒、ソフトクリームを売っている商店は8軒、清涼飲料を売っている商店は9軒です。どの商店も、パン、ソフトクリーム、清涼飲料のいずれか1つは売っています。このとき、パンもソフトクリームも清涼飲料も売っている商店は少なくとも何軒あるか求める問題です。

2. 解き方の手順

まず、ベン図で考えることを念頭に置きます。

全体の商店数を $N$ とし、パンを売っている商店の数を $A$, ソフトクリームを売っている商店の数を $B$, 清涼飲料を売っている商店の数を $C$ とします。

$N = 10$, $A = 6$, $B = 8$, $C = 9$ です。

$A \cup B \cup C$ は、パン、ソフトクリーム、清涼飲料のうち、少なくとも1つを売っている商店の数です。問題文より、どの商店も少なくとも1つは売っているので、$A \cup B \cup C = N = 10$ です。

包除原理を用いて、

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$

が成り立ちます。ここで、求めるべきは$|A \cap B \cap C|$の最小値です。

$10 = 6 + 8 + 9 - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$

$|A \cap B| + |B \cap C| + |C \cap A| - |A \cap B \cap C| = 6 + 8 + 9 - 10 = 13$

$|A \cap B| \le min(|A|, |B|) = min(6, 8) = 6$

$|B \cap C| \le min(|B|, |C|) = min(8, 9) = 8$

$|C \cap A| \le min(|C|, |A|) = min(9, 6) = 6$

$|A \cap B| + |B \cap C| + |C \cap A| \le 6 + 8 + 6 = 20$

$|A \cap B \cap C| = |A \cap B| + |B \cap C| + |C \cap A| - 13$

$|A \cap B \cap C|$ を最小にするには、$|A \cap B|, |B \cap C|, |C \cap A|$ を最小にすれば良い。

$|A \cap B| + |B \cap C| + |C \cap A|$ が最小になるケースを考える。

$|A \cap B \cap C|$ の最小値を求めるために、

$|A \cap B| = x, |B \cap C| = y, |C \cap A| = z$と置く。

$x+y+z-|A \cap B \cap C|=13$

$|A \cup B| = |A| + |B| - |A \cap B|$ より、$|A \cap B| = |A| + |B| - |A \cup B|$

$|A \cup B| \le 10$ なので、$|A \cap B| \ge 6 + 8 - 10 = 4$

同様に、

$|B \cap C| \ge 8 + 9 - 10 = 7$

$|C \cap A| \ge 9 + 6 - 10 = 5$

よって、$|A \cap B| + |B \cap C| + |C \cap A| \ge 4 + 7 + 5 = 16$

$|A \cap B \cap C| = |A \cap B| + |B \cap C| + |C \cap A| - 13 \ge 16 - 13 = 3$

別の考え方として、

ソフトクリームと清涼飲料を売っている商店は少なくとも7軒なので、その7軒全てがパンも売っているとすると $|A \cap B \cap C| = 7$ となりそうですが、パンを売っている商店は6軒しかないので矛盾します。

パンを売っている商店の中で、ソフトクリームも清涼飲料も売っていない商店の数が最小になるようにすると、$10 = (6-x)+(8-x)+(9-x)+x$ となるような $x$ の最小値を求めます。

$N = A + B + C - (A \cap B) - (B \cap C) - (C \cap A) + A \cap B \cap C$

$10 = 6 + 8 + 9 - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$

$N(A \cup B \cup C) = 10$

$N(A) = 6$

$N(B) = 8$

$N(C) = 9$

$N(A \cap B \cap C) \geq N(A) + N(B) + N(C) - 2N(A \cup B \cup C)$

$N(A \cap B \cap C) \geq 6 + 8 + 9 - 2 * 10$

$N(A \cap B \cap C) \geq 23 - 20 = 3$

3. 最終的な答え

3 軒