ProblemăFie $A_1, A_2, ..., A_n$ mulţimi de cardinal $n$.
Oricare $2$ mulţimi de mai sus au intersecţia diferită de $\varnothing$ iar intersecţia oricăror $3$ mulţimi este $\varnothing$.
Să se arate că $|A_1 \cup A_2 \cup ... \cup A_n | \leqslant \frac{n(n+1)}{2}$.
(Problema a fost dată şi la clasa a 9-a, la Etapa finală a Concursului "
Arhimede", 22 ianuarie 2005, Bucureşti)
Rezolvare :
Probabil soluţia autorilor (aşa cum o văd într-o carte) este cea bazată pe
principiul includerii şi al excluderii.
(Eu am abordat un studiu separat, de aceea am postat problema aici .. aşa că ulterior o să discut despre unele aspecte ...)
Principiul (
Formula) :
$|A_1 \cup A_2 \cup ... \cup A_n |$ = $\displaystyle\sum\limits_{i=1}^{n} |A_i| -$ $\displaystyle\sum\limits_{i<j} |A_i \cap A_j| +$ $\displaystyle\sum\limits_{i<j<k} |A_i \cap A_j \cap A_k| - ... +$
$... +(-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n|$
OBS : In cazul a $2$ mulţimi
principiul includerii şi al excluderii este aşa :
$|A \cup B|$ = $|A| + |B| - |A \cap B|$.
(Deci cardinalul unei reuniuni de $2$ mulţimi este suma cardinalelor mulţimilor minus cardinalul intersecţiei mulţimilor)
Revenind la problema de bază, observăm că (în situaţia problemei, cu ipoteza sa) toate sumele care conţin intersecţii de minim 3 mulţimi sunt nule. Deci în problema de faţă principiul devine :
$|A_1 \cup A_2 \cup ... \cup A_n |$ = $\displaystyle\sum\limits_{i=1}^{n} |A_i| -$ $\displaystyle\sum\limits_{i<j} |A_i \cap A_j| \stackrel{not}{=}$ (
**)
Din ipoteză, intersecţia oricăror $2$ submulţimi este nevidă deci $1 \leqslant |A_i \cap A_j|$ sau $- |A_i \cap A_j| \leqslant -1$.
Atunci după (
**) se poate continua aşa :
(
**) $\leqslant \displaystyle\sum\limits_{i=1}^{n} n - \displaystyle\sum\limits_{i<j} 1$ $= n^2 - \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$
QEDPS. O discuţie cu înţelegerea "mecanismului" în cazul acestei probleme, plus $2$ soluţii (fără principiul includerii şi al excluderii) şi o completare cu exemplu de mulţimi $A_i$ care realizează maximul într-o postare ulterioară.
