Ukryta treść:
Zbiory parzyste
- mol_ksiazkowy
- Użytkownik
- Posty: 11373
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Zbiory parzyste
Zbiór \(\displaystyle{ X}\) nazywa się parzystym, jeśli ma parzystą liczbę elementów. Udowodnić, że jeśli \(\displaystyle{ S_1,...,S_n}\) są różnymi parzystymi podzbiorami zbioru \(\displaystyle{ \{ 1,..., n \}}\), przy czym \(\displaystyle{ n}\) jest liczbą parzystą, to istnieją \(\displaystyle{ i \neq j}\) takie, że \(\displaystyle{ S_i \cap S_j}\) też jest zbiorem parzystym.
- arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Zbiory parzyste
Pokażę szkic
Otóż Mamy zbiór S parzysty i interesować nas będą tylko jego podzbiory parzyste, oznaczmy rodzinę podzbiorów parzystych przez \(\displaystyle{ PP(S)}\)
Nie musimy uwzględniać zbioru pustego...
Popatrzmy rodzinę PP(S) jako graf , gdzie wierzchołkami grafu będę elementy \(\displaystyle{ PP(S)}\)
I teraz jeżeli: \(\displaystyle{ S_{i}, S_{j} \in PP(S)}\) to łączymy je krawędzią, jeżeli \(\displaystyle{ S_{i} \cap S_{j} \in PP(S)}\) jest nieparzysty
Jeżeli parzysty jest iloczyn to nie łączymy krawędzią...
Więc jeżeli ma zachodzić teza zadania, to trzeba udowodnić, że klika o rozmiarze \(\displaystyle{ n}\) nie istnieje...
Dla \(\displaystyle{ n=2}\), sprawa jest trywialna tu nie ma co robić, dla \(\displaystyle{ n=4}\) mamy: na obrazku:
Jak widać kliki o rozmiarze 4 brak a zbiór:\(\displaystyle{ \left\{ 1,2,3,4\right\} }\) jest wierzchołkiem izolowanym...
Można wykonać założenie indukcyjne, że dla pewnego \(\displaystyle{ n}\) parzystego nie istnieje klika o rozmiarze \(\displaystyle{ n}\) w Zbiorze \(\displaystyle{ PP(S_{n})}\)
Teza będzie, że w Zbiorze \(\displaystyle{ PP(S_{n+2})}\) nie ma kliki o rozmiarze \(\displaystyle{ n+2}\)...
Z założenia indukcyjnego wiemy, że żeby istniała klika o rozmiarze \(\displaystyle{ n+2}\) w \(\displaystyle{ PP(S_{n+2})}\) muszą do niej należeć
punkty jako zbiory \(\displaystyle{ p_{n}=\left\{ 1,2,3,...,n\right\} }\) bo zbiory o niższej mocy nie tworzą kliki nawet o rozmiarze \(\displaystyle{ n}\) w tej rodzinie...
Jeżeli byśmy założyli , że klika o rozmiarze \(\displaystyle{ n+2}\) jest utworzona z punktów typu \(\displaystyle{ p_{n}}\) to byłby błąd ponieważ każdy punkt tego typu może być jedynie incydentny z \(\displaystyle{ {n \choose n-1} =n}\) zbiorami...
Więc wśród zbiorów parzystych o długości \(\displaystyle{ n}\) nie można utworzyć szukanej kliki. Można się dalej bawić i zakładać, że istnieje klika w której jest \(\displaystyle{ n+2}\) punktów typu \(\displaystyle{ p_{n} \wedge p_{i}, i<n}\), i dowodzić sprzeczności...
Otóż Mamy zbiór S parzysty i interesować nas będą tylko jego podzbiory parzyste, oznaczmy rodzinę podzbiorów parzystych przez \(\displaystyle{ PP(S)}\)
Nie musimy uwzględniać zbioru pustego...
Popatrzmy rodzinę PP(S) jako graf , gdzie wierzchołkami grafu będę elementy \(\displaystyle{ PP(S)}\)
I teraz jeżeli: \(\displaystyle{ S_{i}, S_{j} \in PP(S)}\) to łączymy je krawędzią, jeżeli \(\displaystyle{ S_{i} \cap S_{j} \in PP(S)}\) jest nieparzysty
Jeżeli parzysty jest iloczyn to nie łączymy krawędzią...
Więc jeżeli ma zachodzić teza zadania, to trzeba udowodnić, że klika o rozmiarze \(\displaystyle{ n}\) nie istnieje...
Dla \(\displaystyle{ n=2}\), sprawa jest trywialna tu nie ma co robić, dla \(\displaystyle{ n=4}\) mamy: na obrazku:
Jak widać kliki o rozmiarze 4 brak a zbiór:\(\displaystyle{ \left\{ 1,2,3,4\right\} }\) jest wierzchołkiem izolowanym...
Można wykonać założenie indukcyjne, że dla pewnego \(\displaystyle{ n}\) parzystego nie istnieje klika o rozmiarze \(\displaystyle{ n}\) w Zbiorze \(\displaystyle{ PP(S_{n})}\)
Teza będzie, że w Zbiorze \(\displaystyle{ PP(S_{n+2})}\) nie ma kliki o rozmiarze \(\displaystyle{ n+2}\)...
Z założenia indukcyjnego wiemy, że żeby istniała klika o rozmiarze \(\displaystyle{ n+2}\) w \(\displaystyle{ PP(S_{n+2})}\) muszą do niej należeć
punkty jako zbiory \(\displaystyle{ p_{n}=\left\{ 1,2,3,...,n\right\} }\) bo zbiory o niższej mocy nie tworzą kliki nawet o rozmiarze \(\displaystyle{ n}\) w tej rodzinie...
Jeżeli byśmy założyli , że klika o rozmiarze \(\displaystyle{ n+2}\) jest utworzona z punktów typu \(\displaystyle{ p_{n}}\) to byłby błąd ponieważ każdy punkt tego typu może być jedynie incydentny z \(\displaystyle{ {n \choose n-1} =n}\) zbiorami...
Więc wśród zbiorów parzystych o długości \(\displaystyle{ n}\) nie można utworzyć szukanej kliki. Można się dalej bawić i zakładać, że istnieje klika w której jest \(\displaystyle{ n+2}\) punktów typu \(\displaystyle{ p_{n} \wedge p_{i}, i<n}\), i dowodzić sprzeczności...
- Załączniki
-
- klika.jpg (24.65 KiB) Przejrzano 420 razy
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Zbiory parzyste
Zacząłem czytać i od razu stanąłem na zdaniu:
\(\displaystyle{ \begin{cases} S_n=\{1,n\} \\ S_i=\{i, i+1\} &\text{dla }i \neq n \end{cases} }\)
podobnie jak w ukrytej treści zadania kontrprzykładem dla zbiorów o nieparzystej liczby elementów są układy z podzbiorów \(\displaystyle{ S_i=S \setminus \left\{ i\right\} }\) .
Gdyby założyć, że zbiór pusty nie jest parzysty, to od razu nasuwa się kontrprzykład:
\(\displaystyle{ \begin{cases} S_n=\{1,n\} \\ S_i=\{i, i+1\} &\text{dla }i \neq n \end{cases} }\)
podobnie jak w ukrytej treści zadania kontrprzykładem dla zbiorów o nieparzystej liczby elementów są układy z podzbiorów \(\displaystyle{ S_i=S \setminus \left\{ i\right\} }\) .
Ostatnio zmieniony 6 gru 2022, o 11:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Zbiory parzyste
Przecież nie napisałem, że tak mówiłeś.
I właśnie to mnie zdziwiło. Bez założenia, że zbiór pusty jest parzysty, teza jest nieprawdziwa.
Dziś, czytając dalej powyższy szkic dowodu widzę, że nie tylko go uwzględniasz, ale i używasz zbioru pustego jako parzystego (to np: krawędzie grafu dopełniającego graf z załącznika)
Inne wątpliwości:
Mi się wydaje, że punkt typu \(\displaystyle{ p_n}\) jest połączony z \(\displaystyle{ 2n}\) punktami tego typu.
Intuicja mi mówi, że właśnie ta ''zabawa'' to clou dowodu.arek1357 pisze: ↑27 lis 2022, o 20:17 Więc wśród zbiorów parzystych o długości \(\displaystyle{ n}\) nie można utworzyć szukanej kliki. Można się dalej bawić i zakładać, że istnieje klika w której jest \(\displaystyle{ n+2}\) punktów typu \(\displaystyle{ p_{n} \wedge p_{i}, i<n}\), i dowodzić sprzeczności...
- arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Zbiory parzyste
Masz rację tam są luki i nie jest to dograne...
Dodano po 1 godzinie 14 minutach 48 sekundach:
Sprawa jest tego typu, że nie mówiłem o zbiorze pustym ponieważ, w przedstawionym grafie będzie figurował jako punkt izolowany a więc niepotrzebny do rozważań w grafie istotne są tylko zbiory parzyste od mocy dwa do mocy \(\displaystyle{ n-2}\)
Doszedłem do tego, że taki graf spójny będzie miał:
\(\displaystyle{ {n \choose 2} +{n \choose 4}+...+ {n \choose n-2}=2^{n-1}-2 }\) - wierzchołków, a każdy wierzchołek będzie miał:
\(\displaystyle{ 2^{n-2}}\) - stopień...
Daje nam to graf spójny i regularny, jeżeli wykażemy w nim brak kliki stopnia \(\displaystyle{ n}\) to teza zadania będzie spełniona...
Jedynie co to tu indukcja będzie do bani...
Dodano po 1 godzinie 14 minutach 48 sekundach:
Sprawa jest tego typu, że nie mówiłem o zbiorze pustym ponieważ, w przedstawionym grafie będzie figurował jako punkt izolowany a więc niepotrzebny do rozważań w grafie istotne są tylko zbiory parzyste od mocy dwa do mocy \(\displaystyle{ n-2}\)
Doszedłem do tego, że taki graf spójny będzie miał:
\(\displaystyle{ {n \choose 2} +{n \choose 4}+...+ {n \choose n-2}=2^{n-1}-2 }\) - wierzchołków, a każdy wierzchołek będzie miał:
\(\displaystyle{ 2^{n-2}}\) - stopień...
Daje nam to graf spójny i regularny, jeżeli wykażemy w nim brak kliki stopnia \(\displaystyle{ n}\) to teza zadania będzie spełniona...
Jedynie co to tu indukcja będzie do bani...
-
- Użytkownik
- Posty: 1404
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 61 razy
- Pomógł: 83 razy
Re: Zbiory parzyste
Dzisiaj próbowałem to zadanie rozwiązać. Niestety, nie udało się- poddaje się na dziś. I, generalnie, to zadanie jest dla mnie mało ciekawe, bo nie uogólnia się na zbiory dowolne. Bo myślałem nawet, że mam tu kontrprzykład dla dwóch zbiorów, a dowcip polega na tym, że w takim wypadku mamy jedynie tylko dwa elementy. I ogólnie, problem leży w tym, że mamy za mało, bo tyle samo, elementów w stosunku do ilości zbiorów- gdybyśmy mogli używać całego zbioru liczb naturalnych, to wtedy łatwo można wskazać dwa zbiory parzyste, których przekrój jest zbiorem nieparzystym: \(\displaystyle{ A= \left\{ 0,1,2,3\right\}, B=\left\{ 3,4,5,6\right\} , }\) tylko wtedy potrzebujemy aż siedmiu elementów. Gdy to zauważyłem, to przestało mi się to zadanie podobać, bo ja jestem miłośnik zbiorów ogólnych. Przedstawię tu jedynie swoją próbę rozwiązania tego zadania.
PRÓBA DOWODU:
Nie wprost:
Jeśli przekrój każdych dwóch różnych zbiorów jest nieparzysty, to wtedy taki przekrój jest niepusty, bo \(\displaystyle{ 0}\)- moc zbioru pustego, jest liczbą parzystą. Komu nie podoba się taki argument, to może inaczej: Jeśli wśród naszych zbiorów są dwa różne zbiory rozłączne, to ich przekrój jest pusty- zbiór parzysty, i teza zadania jest spełniona. Pozostaje zatem rozważyć przypadek przeciwny, czyli gdy każde dwa różne zbiory spośród naszych zbiorów \(\displaystyle{ S _{1}, S _{2}, \ldots, S _{n} }\), gdy się przecinają (niepusto). Ale jak mamy takie dwa zbiory \(\displaystyle{ A,B}\) o przekroju nieparzystym, to ponieważ zbiory \(\displaystyle{ A,B}\) są parzyste, to różnice \(\displaystyle{ A \setminus B=A \setminus \left( A \cap B\right) }\) I \(\displaystyle{ B \setminus A=B \setminus \left( A \cap B\right) }\) są nieparzyste, i to dla dowolnych dwóch różnych zbiorów spośród naszych zbiorów. I trzeba jakoś dojść do sprzeczności...
Może by zastosować taki chwyt, że skoro każde dwa różne zbiory, spośród naszych zbiorów, przecinają się, to można by ustalić jeden taki zbiór, i zastosować fakt, że ten zbiór (niepusty) będzie przecinał przecięcie tych wszystkich (skończenie wielu) zbiorów, no bo jak dany zbiór przecina dwa inne zbiory, to ten dany zbiór przecina również przecięcie tych dwóch zbiorów.
Może to komuś pomoże.
Dodano po 18 godzinach 25 minutach 52 sekundach:
Wystarczy rozważyć jako dany zbiór \(\displaystyle{ \left\{ 0,2\right\} }\), a jako dwa kolejne zbiory wystarczy rozważyć: \(\displaystyle{ \left\{ 0,1\right\} }\) i \(\displaystyle{ \left\{ 1,2\right\} }\).
Wtedy \(\displaystyle{ 0 \in \left\{ 0,2\right\} \cap \left\{ 0,1\right\}, }\) czyli zbiór \(\displaystyle{ \left\{ 0,2\right\} }\) przecina zbiór \(\displaystyle{ \left\{ 0,1\right\}, }\) i podobnie \(\displaystyle{ 2 \in \left\{ 0,2\right\} \cap \left\{ 1,2\right\};}\) podczas gdy: \(\displaystyle{ \left\{ 0,2\right\} \cap \left( \left\{ 0,1\right\} \cap \left\{ 1,2\right\} \right)= \left\{ 0,2\right\} \cap \left\{ 1\right\}= \emptyset,}\) czyli zbiór \(\displaystyle{ \left\{ 0,2\right\} }\) nie przecina przecięcia zbiorów \(\displaystyle{ \left\{ 0,1\right\} }\) i \(\displaystyle{ \left\{ 1,2\right\}, }\) niestety.
PRÓBA DOWODU:
Nie wprost:
Jeśli przekrój każdych dwóch różnych zbiorów jest nieparzysty, to wtedy taki przekrój jest niepusty, bo \(\displaystyle{ 0}\)- moc zbioru pustego, jest liczbą parzystą. Komu nie podoba się taki argument, to może inaczej: Jeśli wśród naszych zbiorów są dwa różne zbiory rozłączne, to ich przekrój jest pusty- zbiór parzysty, i teza zadania jest spełniona. Pozostaje zatem rozważyć przypadek przeciwny, czyli gdy każde dwa różne zbiory spośród naszych zbiorów \(\displaystyle{ S _{1}, S _{2}, \ldots, S _{n} }\), gdy się przecinają (niepusto). Ale jak mamy takie dwa zbiory \(\displaystyle{ A,B}\) o przekroju nieparzystym, to ponieważ zbiory \(\displaystyle{ A,B}\) są parzyste, to różnice \(\displaystyle{ A \setminus B=A \setminus \left( A \cap B\right) }\) I \(\displaystyle{ B \setminus A=B \setminus \left( A \cap B\right) }\) są nieparzyste, i to dla dowolnych dwóch różnych zbiorów spośród naszych zbiorów. I trzeba jakoś dojść do sprzeczności...
Może by zastosować taki chwyt, że skoro każde dwa różne zbiory, spośród naszych zbiorów, przecinają się, to można by ustalić jeden taki zbiór, i zastosować fakt, że ten zbiór (niepusty) będzie przecinał przecięcie tych wszystkich (skończenie wielu) zbiorów, no bo jak dany zbiór przecina dwa inne zbiory, to ten dany zbiór przecina również przecięcie tych dwóch zbiorów.
Może to komuś pomoże.
Dodano po 18 godzinach 25 minutach 52 sekundach:
Przepraszam, to niestety jest nieprawda.Jakub Gurak pisze: ↑9 gru 2022, o 22:42 jak dany zbiór przecina dwa inne zbiory, to ten dany zbiór przecina również przecięcie tych dwóch zbiorów.
Wystarczy rozważyć jako dany zbiór \(\displaystyle{ \left\{ 0,2\right\} }\), a jako dwa kolejne zbiory wystarczy rozważyć: \(\displaystyle{ \left\{ 0,1\right\} }\) i \(\displaystyle{ \left\{ 1,2\right\} }\).
Wtedy \(\displaystyle{ 0 \in \left\{ 0,2\right\} \cap \left\{ 0,1\right\}, }\) czyli zbiór \(\displaystyle{ \left\{ 0,2\right\} }\) przecina zbiór \(\displaystyle{ \left\{ 0,1\right\}, }\) i podobnie \(\displaystyle{ 2 \in \left\{ 0,2\right\} \cap \left\{ 1,2\right\};}\) podczas gdy: \(\displaystyle{ \left\{ 0,2\right\} \cap \left( \left\{ 0,1\right\} \cap \left\{ 1,2\right\} \right)= \left\{ 0,2\right\} \cap \left\{ 1\right\}= \emptyset,}\) czyli zbiór \(\displaystyle{ \left\{ 0,2\right\} }\) nie przecina przecięcia zbiorów \(\displaystyle{ \left\{ 0,1\right\} }\) i \(\displaystyle{ \left\{ 1,2\right\}, }\) niestety.