drogi krola szachowego/Ustawienie podzbiorow w ciag

[pred]

Ile jest róznych najkrótszych dróg króla szachowego z pola e1 do pola e8? Do pola a8 ?

rozrysowalem to sobie, i zaznaczylem na rysunku te najkrótsze drogi. Król może posuwać się tylko do góry aby droga była najkrótrza.

Przypadek do pola e8

Więc tak:
1. G - bezposrednio na góre
2. L - na lewo(ale też do góry) np z e1 na d2.
3. P - na prawo(ale też do góry) np z e1 na f2.

Trzy przypadki dróg:
1. L=1, P=1, G=5
2. L=2, P=2, G=3
3. L=3, L=3, G=1

Pozniej wybieram ilosc mozliwosci na jakie mogę ustawić L,P,G
Dla pierwszej drogi:
np. LPGGGGG lub LGGPGGG
Czyli da się to zapisać w ten spsób: (możliwości ustawień)

\(\displaystyle{ L={7 \choose 1} P={6 \choose 1} G={5 \choose 5}}\)

No i teraz pytanie, czy moje rozumowanie jest ok ? Jeśli nie to proszę o rozpisanie tego w miarę przystępny sposób ( też do pola a8).


Drugie zadanko to.

Udowodnij, ze wszystkie podzbiory zbioru skonczonego mozna ustawic w ciag, ktorego kolejne wyrazy roznia sie jendym elmentem.

Tego nie moge niestety w ogole ruszyc.

[dariusz_konieczny]

Nie jestem matematykiem, ale informatykiem.
Stąd to drugie zadanie skojarzyło mi się od razu z binarnym kodem Graya i po chwili zastanowienia wydaje mi się, że dokładnie o niego chodzi. Podpowiadać dalej, czy chcesz sam najpierw poczytać o tym kodzie?

[pred]

Hm tez akurat jestem na infie i mialem skojarzenia z tym kodem, ale nie przyszło mi do głowy jak zastosować to do systemu dziesiętnego. Czas troche nagli, więc poprosilbym o jakies podpowiedzi, ew rozwiazanie.

[dariusz_konieczny]

Każda pozycja w kodzie binarnym będzie oznaczać, czy element jest w podzbiorze (1), czy element nie jest w podzbiorze (0). Teraz idąc kolejnymi liczbami binarnymi kodu Graya (których zapis binarny różni się tylko na jednym bicie) otrzymujemy kolejne podzbiory różniące się obecnością lub nie jednego elementu.
Przykład, zbiór 3-elementowy {A,B,C} Pierwsza pozycja binarna to A, druga to B, trzecia C:
000 - {}
001 - {C}
011 - {B,C}
010 - {B}
110 - {A,B}
111 - {A,B,C}
101 - {A,C}
100 - {A}