Równoliczność podzbiorów.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Matiks21
Użytkownik
Użytkownik
Posty: 562
Rejestracja: 20 maja 2013, o 16:33
Płeć: Mężczyzna
Lokalizacja: Kielce
Podziękował: 98 razy

Równoliczność podzbiorów.

Post autor: Matiks21 »

Cześć, znalazłem takie zadanie.

"Udowodnij że wśród podzbiorów dowolnego niepustego zbioru skończonego A połowę stanowią podzbiory o parzystej liczbie elementów."

dla przypadku zbioru o mocy nieparzystej dowód jest prosty, łączysz podzbiory tego zbioru w pary i wychodzi taka sama liczb parzystych i nie parzystych podzbiorów. Ale w przypadku zbioru o mocy parzystej nie mam pojęcia jak się za to zabrać.

Pomoże ktoś?
kolegasafeta
Użytkownik
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

Równoliczność podzbiorów.

Post autor: kolegasafeta »

Mam pewien pomysł. Wyróżnijmy jakiś element zbioru. Weźmy teraz dowolny podzbiór. Jeżeli zawiera wyróżniony element, to wyrzucamy go. Jeżeli nie zawiera, to dodajemy. Tak określona funkcja powinna być bijekcją zbioru podzbiorów. Dodatkowo każdemu zbiorowi parzystemu przyporządkowuje nieparzysty i na odwrót. Więc muszą być równoliczne.
Matiks21
Użytkownik
Użytkownik
Posty: 562
Rejestracja: 20 maja 2013, o 16:33
Płeć: Mężczyzna
Lokalizacja: Kielce
Podziękował: 98 razy

Równoliczność podzbiorów.

Post autor: Matiks21 »

Chyba wpadliśmy na podobny pomysł, napisałem podobny bo nie określiłeś przyporządkowania dokładnie ale chyba to to samo.

Dowolnemu podzbiorowi \(\displaystyle{ B}\) zbioru \(\displaystyle{ A}\) do którego należy element wyrózniony np. \(\displaystyle{ a \in A}\) przyporządkujmy ten sam zbiór ale z elementem wyróznionym a. Czyli \(\displaystyle{ B}\) \(\displaystyle{ \rightarrow}\) \(\displaystyle{ B \cup \{a\}}\)

teraz jest to funkcja różnowartościowa ponieważ dla danego zbioru istnieje tylko jeden zbiór mu tożsamy z elementem wyróżnionym. I jest to funkcja "na" ponieważ dla każdego\(\displaystyle{ B \cup \{a\}}\) istnieje \(\displaystyle{ B}\) co więcej jest tylko jeden taki zbiór.

Zatem połączylismy w pary wszystkie zbiory i są to przyporządowania z podzbioru o mocy k na podzbiór o mocy k+1 gdzie k jest jakąś liczbą naturalną mniejszą od n.

Dzięki.


P.S. jednak określiłeś ale nie zrozumiałem za pierwszym razem:P
ODPOWIEDZ