doorsnede van verzamelingen
Opgave - APMC 1978 dag 2 vraag 2
De verzamelingen $A_1,A_2,...,A_{1978}$ hebben elk 40 elementen, en de doorsnede tussen elke twee verschillende verzamelingen bevat juist 1 element. Toon aan dat de doorsnede van al de verzamelingen ook juist 1 element bevat.
- login om te reageren
Oplossing
Veronderstel dat het niet zo is:
Neem $A_1$ en bekijk het gemeenschappelijk element met de $1977$ andere verzamelingen.
Omdat $\frac {1977}{40}>41$ is er een verzameling $U$ van ten minste $41$ verzamelingen met allen eenzelfde element $a$ als doorsnede(duivenhokprincipe). (Het kan natuurlijk strenger, maar dat is hier niet nodig).
$U = \{ A_i \mid a \in A_i;i=1,2\cdots 1978\}$.
Wegens ons veronderstelde is $41<|U|<1978$.
Bekijk nu een verzameling $A_{x}$ die niet tot $U$ behoort.
$A_{x}$ heeft nu met elk van de verzamelingen uit $U$ een ander element $a_{y}$ gemeenschappelijk, maar $U$ heeft $41$ elementen en $A_{x}$ slechts $40$ dus zijn er twee verzamelingen uit $U$ die hetzelfde element ($not= a$ gemeenschappelijk hebben (duivenhokprincipe).
Tegenspraak, omdat deze twee verzamelingen nu $2$ elementen gemeenschappelijk hebben (voorgaand element en ook $a$).
Dus de vraag is waar.