Udowodnij, że można ustawić w ciąg

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Udowodnij, że można ustawić w ciąg

Post autor: max123321 »

Udowodnij, że wszystkie podzbiory zbioru \(\displaystyle{ n}\)-elementowego \(\displaystyle{ n \ge 1}\) można ustawić w ciąg \(\displaystyle{ \left\langle X_1,....,X_{2^n}\right\rangle}\) w taki sposób, że
\(\displaystyle{ \forall i<2^n \left| X_i\right| \neq \left| X_{i+1}\right|}\) oraz \(\displaystyle{ \left| X_{2^n}\right| \neq \left| X_1\right|}\).

Jak to zrobić?

Ponadto wykaż, że można wymagać, aby dla każdego \(\displaystyle{ i<2^n}\) zbiory \(\displaystyle{ X_i,X_{i+1}}\) różniły się jednym elementem.

Jak to zrobić?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Udowodnij, że można ustawić w ciąg

Post autor: Premislav »

Pokażę dla zbioru czteroelementowego \(\displaystyle{ \left\{ a,b,c,d\right\}}\):
\(\displaystyle{ X_1=\varnothing, \\ X_2=\left\{ a\right\}, \\ X_3=\left\{ a,b\right\}\\X_4=\left\{ b\right\}\\X_5=\left\{ b,c\right\}\\X_6=\left\{ c\right\}\\X_7=\left\{ c, d\right\}\\X_8=\left\{ d\right\}\\X_9=\left\{ b,d\right\}\\X_{10}=\left\{ a,b,d\right\}\\X_{11}=\left\{ a,d\right\}\\X_{12}=\left\{a,c,d\right\}\\X_{13}=\left\{ a,c\right\}\\X_{14}=\left\{ a,b,c\right\}\\X_{15}=\left\{ a,b,c,d\right\}\\X_{16}=\left\{ b,c,d\right\}}\)

Może patrząc na to, wpadniesz na jakiś pomysł (wsk. zwróć uwagę, co by się stało, gdyby usunąć wszystkie zbiory, do których należy element \(\displaystyle{ d}\) i spróbuj na to spojrzeć w drugą stronę).
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Re: Udowodnij, że można ustawić w ciąg

Post autor: max123321 »

No widzę, że dla dowolnego zbioru \(\displaystyle{ n}\) elementowego na pierwszym miejscu ustawiamy zbiór pusty, potem na drugim dowolny zbiór jednoelementowy, potem na przemian dowolny zbiór dwuelementowy i jednoelementowy tak, żeby się nie powtarzały, aż do wyczerpania zbiorów jednoelementowych, potem na przemian zbiory trzy i dwuelementowe, aż do wyczerpania dwuelementowych i tak dalej. W ten sposób? Ale to jakieś dziwne rozwiązanie, a po drugie nie wiem jak to zapisać. Pomożesz trochę?
ODPOWIEDZ