Zbiory parzyste

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Zbiory parzyste

Post autor: mol_ksiazkowy »

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.

Ukryta treść:    
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zbiory parzyste

Post autor: arek1357 »

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...
Załączniki
klika.jpg
klika.jpg (24.65 KiB) Przejrzano 417 razy
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Zbiory parzyste

Post autor: kerajs »

Zacząłem czytać i od razu stanąłem na zdaniu:
arek1357 pisze: 27 lis 2022, o 20:17 Nie musimy uwzględniać zbioru pustego...
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.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zbiory parzyste

Post autor: arek1357 »

Ja nigdzie nie mówiłem, że zbiór pusty jest nieparzysty tylko nie brałem go pod uwagę ponieważ nie był mi do niczego potrzebny...
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Zbiory parzyste

Post autor: kerajs »

arek1357 pisze: 6 gru 2022, o 00:17 Ja nigdzie nie mówiłem, że zbiór pusty jest nieparzysty
Przecież nie napisałem, że tak mówiłeś.
arek1357 pisze: 6 gru 2022, o 00:17 Ja nigdzie nie mówiłem, że zbiór pusty jest nieparzysty tylko nie brałem go pod uwagę ponieważ nie był mi do niczego potrzebny...
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:
arek1357 pisze: 27 lis 2022, o 20:17 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...
Mi się wydaje, że punkt typu \(\displaystyle{ p_n}\) jest połączony z \(\displaystyle{ 2n}\) punktami tego typu.
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...
Intuicja mi mówi, że właśnie ta ''zabawa'' to clou dowodu.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zbiory parzyste

Post autor: arek1357 »

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...
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory parzyste

Post autor: Jakub Gurak »

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. :mrgreen: 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. :lol:

Dodano po 18 godzinach 25 minutach 52 sekundach:
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.
Przepraszam, to niestety jest nieprawda.

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. :?
ODPOWIEDZ