fajne podzbiory

[bediej]

rozpatrzmy podzbiory zbioru {1..3n}
podzbiór jest fajny jeśli nie istnieją w nim 2 elementy które różnią się o n (w szczególności zbiór pusty jest fajny)
ile jest fajnych podzbiorów w zależności od n

[mol_ksiazkowy]

ah luzna idea , X={1..3n} jest suma A={1, ...n} B={n+1, ...2n} i C={2n+1, ...3n} Na pewno o ile istnieja elementy z wybranym pozbiorze X a i b, takie ze a-b=n, to jeden z nich jest w B, zas pozostały w A lub C. Stad wynika ze wpierw wybieramy podzbir k elementowy z B, i "usuwamy" z A i C po k elementow, wynik
w=\(\displaystyle{ \sum_{k=0}^n 2^{n-k} \ 2^{n-k}}\)
np dla n=1 , w=5 tj
\(\displaystyle{ \emptyset}\)
\(\displaystyle{ \{ 1\}}\)
\(\displaystyle{ \{ 2\}}\)
\(\displaystyle{ \{ 3\}}\)
\(\displaystyle{ \{ 1, 3 \}}\)

[bediej]

ehh.. powiedzmy tak .. zaczynasz to robic tak jak ja to zrobilem na egzaminie , ale jak zwykle w takich przypadkach mozna prościej:
rozpatrzmy trojki elementow { 1 (n+1) (2n+1)} { 2 (n+2) (2n+2) } itd.. wybory dla kazdej z tych trojek sa niezalezne (tzn na logike fajnosc zbioru decyduje sie na poziomie trojek a nie zaleznosci miedzy nimi)

dla kazdej trojki mozemy
1. wybrac lewy element
2. wybrac prawy element
3. wybrac srodkowy element
4. wybrac lewy i prawy element
5. nie wybrac zadnego

no to wszystkich takich fajnych zbiorow jest 5^n .. fin