Jak udowodnić, że wszystkie pozdzbiory zbioru \(\displaystyle{ n}\)-elementowego można ustawić w ciąg \(\displaystyle{ X_1,X_2,...,X_{2^n}}\) w taki sposób, że
\(\displaystyle{ \forall i<2^n \ \ |X_i| \neq |X_{i+1}}\)
oraz
\(\displaystyle{ |X_{2^n} |\neq |X_1|}\)?
ustawianie podzbiorów w ciąg
-
- 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
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
ustawianie podzbiorów w ciąg
Wydaje mi się, że indukcja tutaj zadziała bardzo dobrze.
Zakładam dla uproszczenia, że elementami zbioru są liczby od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\).
W kroku pierwszym mamy \(\displaystyle{ n=1}\) oraz?
W kroku drugim mamy dobrze ułożone podzbiory \(\displaystyle{ \{1,\ldots,n\}}\) i chcemy ułożyć poprawnie \(\displaystyle{ \{1,\ldots,n+1\}}\)
Usuń \(\displaystyle{ n+1}\) i dostaniesz zbiór, który możesz uporządkować. Jak teraz dorobić resztę? Może coś Ci przyjdzie do głowy? Założenie drugie jest tutaj kluczowe i umożliwia uporządkowanie przynajmniej w tym rozwiązaniu, które ja wymyśliłem.
Zakładam dla uproszczenia, że elementami zbioru są liczby od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\).
W kroku pierwszym mamy \(\displaystyle{ n=1}\) oraz?
W kroku drugim mamy dobrze ułożone podzbiory \(\displaystyle{ \{1,\ldots,n\}}\) i chcemy ułożyć poprawnie \(\displaystyle{ \{1,\ldots,n+1\}}\)
Usuń \(\displaystyle{ n+1}\) i dostaniesz zbiór, który możesz uporządkować. Jak teraz dorobić resztę? Może coś Ci przyjdzie do głowy? Założenie drugie jest tutaj kluczowe i umożliwia uporządkowanie przynajmniej w tym rozwiązaniu, które ja wymyśliłem.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
ustawianie podzbiorów w ciąg
Rozważmy graf, którego wierzchołkami są podzbiory danego zbioru \(\displaystyle{ n}\)-elementowego, a dwa takie podzbiory są połączone krawędzią wtedy i tylko wtedy gdy mają różną liczbę elementów. Nietrudno zauważyć, że teza zadania sprowadza się tego, że graf jest hamiltonowski, a to łatwo wynika na przykład z tw. Diraca.
Edit: przecież można jeszcze prościej - dokładnie połowa podzbiorów ma parzystą ilość elementów, a połowa nieparzystą.
Q.
Edit: przecież można jeszcze prościej - dokładnie połowa podzbiorów ma parzystą ilość elementów, a połowa nieparzystą.
Q.
-
- 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
ustawianie podzbiorów w ciąg
Drugie rozwiązanie zrozumiałem, a z wykorzystaniem tego faktu o równoliczności parzystych i nieparzystych faktycznie jest natychmiastowe, dzięki ! Ale pierwszego rozwiązania z indukcją jeszcze nie rozumiem.
Uzupełnienie: bijekcję z "parzystych" w "nieparzyste" można zrobić wyróżniając element i w zależności od obecności tego elementu w zbiorze lub braku odpowiednio wyrzucamy go lub dokładamy.
Uzupełnienie: bijekcję z "parzystych" w "nieparzyste" można zrobić wyróżniając element i w zależności od obecności tego elementu w zbiorze lub braku odpowiednio wyrzucamy go lub dokładamy.
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
ustawianie podzbiorów w ciąg
Takie rozwiązanie akurat przyszło mi do głowy. Mogę je przedstawić później, jeśli chcesz. Ale jest dość złożone - powiedziałbym wręcz trudne rozwiązanie prostego problemu. Prostego dzięki temu:kolegasafeta pisze: Ale pierwszego rozwiązania z indukcją jeszcze nie rozumiem.
Że też to jest takie trywialne... Widziałem to zadanie wiele razy i nigdy nie przyszło mi takie rozwiązanie do głowy.Qń pisze: przecież można jeszcze prościej - dokładnie połowa podzbiorów ma parzystą ilość elementów, a połowa nieparzystą..