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ć?
Udowodnij, że można ustawić w ciąg
- Premislav
- 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
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ę).
\(\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ę).
-
- 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
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ę?