element wspólny rodziny zbiorów
-
kolegasafeta
- Użytkownik
- Posty: 209
- Rejestracja: 26 lis 2009, o 23:45
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 17 razy
- Pomógł: 8 razy
element wspólny rodziny zbiorów
Danych jest \(\displaystyle{ 1978}\) zbiorów, z których każdy zawiera \(\displaystyle{ 40}\) elementów. Każde dwa z tych zbiorów mają dokładnie jeden element wspólny. Udowodnij, że istnieje elemenet należący do wszystkich \(\displaystyle{ 1978}\) zbiorów.
Ostatnio zmieniony 21 sie 2013, o 23:31 przez kolegasafeta, łącznie zmieniany 1 raz.
element wspólny rodziny zbiorów
Tych zbiorów jest \(\displaystyle{ 1987}\) czy \(\displaystyle{ 1978}\)?
Proszę zacząć od skorzystania z zasady szufladkowej. Ustalamy jakiś zbiór \(\displaystyle{ A}\). Każdy z pozostałych zbiorów ma jeden element wspólny ze zbiorem \(\displaystyle{ A}\), zatem któryś z elementów \(\displaystyle{ A}\) należy do co najmniej ... zbiorów.
Proszę zacząć od skorzystania z zasady szufladkowej. Ustalamy jakiś zbiór \(\displaystyle{ A}\). Każdy z pozostałych zbiorów ma jeden element wspólny ze zbiorem \(\displaystyle{ A}\), zatem któryś z elementów \(\displaystyle{ A}\) należy do co najmniej ... zbiorów.
-
kolegasafeta
- Użytkownik
- Posty: 209
- Rejestracja: 26 lis 2009, o 23:45
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 17 razy
- Pomógł: 8 razy
element wspólny rodziny zbiorów
\(\displaystyle{ 1978}\), już poprawione, przepraszam.
\(\displaystyle{ (1978-1)/40 = 49}\)reszty \(\displaystyle{ 17}\), więc istnieje \(\displaystyle{ 17}\) elementów takich, że każdy występuje w \(\displaystyle{ 51}\) zbiorach
Można wybrać sobie jeden z nich. Ale jakby to dalej pociągnąć?
\(\displaystyle{ (1978-1)/40 = 49}\)reszty \(\displaystyle{ 17}\), więc istnieje \(\displaystyle{ 17}\) elementów takich, że każdy występuje w \(\displaystyle{ 51}\) zbiorach
Można wybrać sobie jeden z nich. Ale jakby to dalej pociągnąć?
element wspólny rodziny zbiorów
Zasada szufladkowa nie mówi, że istnieje aż \(\displaystyle{ 17}\) takich elementów. Istnieje co najmniej jeden element zbioru \(\displaystyle{ A}\), który należy do co najmniej \(\displaystyle{ 50}\) z pozostałych zbiorów. Krótko mówiąc, istnieje pewien element — nazwijmy go \(\displaystyle{ a}\) — który należy do co najmniej \(\displaystyle{ 51}\) zbiorów: \(\displaystyle{ A_1, A_2, \ldots, A_{51}}\).
Dalej można rozumować nie wprost. Załóżmy, że istnieje zbiór \(\displaystyle{ B}\), do którego nie należy \(\displaystyle{ a}\). Wiemy, że
- \(\displaystyle{ B}\) i \(\displaystyle{ A_1}\) mają dokładnie jeden wspólny element \(\displaystyle{ b_1}\),
- \(\displaystyle{ B}\) i \(\displaystyle{ A_2}\) mają dokładnie jeden wspólny element \(\displaystyle{ b_2}\), itd.
Wystarczy jeszcze tylko zauważyć, że wszystkie elementy \(\displaystyle{ b_1, b_2,\ldots}\) muszą być różne, co prowadzi do wniosku, że \(\displaystyle{ B}\) ma ponad \(\displaystyle{ 40}\) elementów wbrew założeniom zadania.
Dalej można rozumować nie wprost. Załóżmy, że istnieje zbiór \(\displaystyle{ B}\), do którego nie należy \(\displaystyle{ a}\). Wiemy, że
- \(\displaystyle{ B}\) i \(\displaystyle{ A_1}\) mają dokładnie jeden wspólny element \(\displaystyle{ b_1}\),
- \(\displaystyle{ B}\) i \(\displaystyle{ A_2}\) mają dokładnie jeden wspólny element \(\displaystyle{ b_2}\), itd.
Wystarczy jeszcze tylko zauważyć, że wszystkie elementy \(\displaystyle{ b_1, b_2,\ldots}\) muszą być różne, co prowadzi do wniosku, że \(\displaystyle{ B}\) ma ponad \(\displaystyle{ 40}\) elementów wbrew założeniom zadania.