Strona 1 z 1
[Kombinatoryka] przecięcia
: 4 wrz 2006, o 11:41
autor: mol_ksiazkowy
Danych jest skończony układ zbiorów: \(\displaystyle{ A_1, ....., A_{1978}}\), z których każdy zawiera 40 elementów. Każde dwa z tych zbiorów \(\displaystyle{ A_i, A_j}\), \(\displaystyle{ i j}\) maja po jednym elemencie wspólnym. Udowodnić, że istnieje element należacy do wszystkich tych zbiorów.
[Kombinatoryka] przecięcia
: 16 wrz 2008, o 18:25
autor: limes123
No to zaczynamy
\(\displaystyle{ \frac{1978}{40}>49}\) czyli co najmniej jeden z elementow w tych zbiorach nalezy do co najmniej 50 zbiorow. Niech beda to zbiory a2, a2, ..., a51 (bez zmniejszania ogolnosci) i zalozmy, ze ten element (powiedzmy X) nalezy do zbioru a1. Jesli x nalezy do kazdego zbioru to teza zachodzi. Jak nie, to istnieje B w ktorym nie ma x, a poniewaz kazda para a2 B,..., a51 B ma element wspolny rozny od B (na mcy warunkow zadania) oraz zadne 2 z tych elementow wspolnych nie sa rowne (bo te a2 a3 ... maja juz element wspolny x), to B musialby miec wiecej niz 40 elementow - sprzecznosc.