ustawianie podzbiorów w ciąg

kolegasafeta · Post autor: **kolegasafeta** » 20 sie 2013, o 23:21

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|}\)?

yorgin · Post autor: **yorgin** » 20 sie 2013, o 23:48

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.

Qń · Post autor: Qń » 21 sie 2013, o 01:10

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.

kolegasafeta · Post autor: **kolegasafeta** » 21 sie 2013, o 11:08

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.

yorgin · Post autor: **yorgin** » 21 sie 2013, o 11:19

kolegasafeta pisze: Ale pierwszego rozwiązania z indukcją jeszcze nie rozumiem.

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:

Qń pisze: przecież można jeszcze prościej - dokładnie połowa podzbiorów ma parzystą ilość elementów, a połowa nieparzystą..

Że też to jest takie trywialne... Widziałem to zadanie wiele razy i nigdy nie przyszło mi takie rozwiązanie do głowy.