[Kombinatoryka] przecięcia
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
mol_ksiazkowy
- Użytkownik
- Posty: 13381
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3425 razy
- Pomógł: 809 razy
[Kombinatoryka] przecięcia
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.
-
limes123
- Użytkownik
- Posty: 665
- Rejestracja: 21 sty 2008, o 22:48
- Płeć: Mężczyzna
- Lokalizacja: Ustroń
- Podziękował: 26 razy
- Pomógł: 93 razy
[Kombinatoryka] przecięcia
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.
\(\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.