Wieże Hanoi, problem Flawiusza

[Watari]

1)Niech \(\displaystyle{ Q _{n}}\) będzie minimalną liczbą ruchów konieczną do przełożenia wieży złożonej z n krążków z A na B przy założeniu, że wszystkie ruchy należy wykonywać zgodnie ze wskazówkami zegara - czyli z A na B, z B na trzeci pręt oraz z trzeciego pręta na A. Niech\(\displaystyle{ R _{n}}\) będzie minimalną liczbą ruchów potrzebną, aby przy tych samych ograniczeniach przenieśc krążki z powrotem z B na A. Pokaż, że:
\(\displaystyle{ Q _{n} = \begin{cases} 0; n=0 \\ 2R _{n-1} + 1; n>0 \end{cases}}\)
\(\displaystyle{ R _{n} = \begin{cases} 0; n=0 \\ Q _{n} + Q _{n-1} + 1; n>0 \end{cases}}\)

Nie należy rozwiązywać tych rekurencji.

2) Flawiusz miał przyjaciela, który został uratowany, gdy był na przedostatniej pozycji. Ile wynosi I(n), numer przedostatniej pozycji, gdy co druga osoba jest eliminowana?

Problem Flawiusza: W okręgu umieszczonych jest n obiektów, następnie eliminowany jest co drugi obiekt, aż pozostanie tylko jeden. Problem polega na wskazaniu tego obiektu, który pozostanie.


Bardzo proszę o pomoc i możliwie szczegółowe wytłumaczenie.

[Zordon]

popraw zapis najpierw

a po drugie, nie każdy zna sformułowanie problemu Flawiusza.
I ogólnie, sądze, że masz te zadania z matematyki konkretnej, z tyłu są rozwiązania jak coś...

[Watari]

Wiem, że są odpowiedzi z tyłu książki, ale te do tych zadań niezbyt mi pomagają.

[Dumel]

ten problem Flawiusza jest dość prosty. jak rozumiem wykreślamy co drugą poczynając od pierwszej, bo inaczej byłoby za łatwo.
wykreślamy więc wszystkie liczby nieparzyste. pozostałe możemy sobie podzielić przez 2. znowu wykreślamy nieparzyste, znowu dzielimy itd. to tak tylko dla lepszego zrozumienia tego co zaraz napiszę, a mianowicie: w \(\displaystyle{ n}\)-tej sekwencji ruchów wykreślamy liczby które są podzielne przez \(\displaystyle{ 2^{n-1}}\) a nie są podzielne przez \(\displaystyle{ 2^n}\). na końcu pozostanie więc liczba \(\displaystyle{ 2^{\lfloor{log_2n} \rfloor}}\)
aha czyli przedostatnia wykreślona liczba jest równa \(\displaystyle{ 2^{\lfloor{log_2n} \rfloor-1}k}\)
gdzie \(\displaystyle{ k}\) jest największą liczbą nieparzystą taką że \(\displaystyle{ 2^{\lfloor{log_2n} \rfloor-1}k \le n}\)
edit: ooo teraz widze że w obiekty są umieszczone na okręgu więc to co napisałem jest źle :/

hmm może coś takiego Ci pomoże:
\(\displaystyle{ f(2^n(2k+1))=2f(2k+1)+1}\)
\(\displaystyle{ f(2k+1)=2g(k+1)-1}\)
\(\displaystyle{ g(2k+1)=2f(k)}\)
\(\displaystyle{ g(2^n(2k+1))=2^{\lfloor nlog_2(2k+1) \rfloor}}\)
g to analogiczna funckja jak f, z tym że zaczynamy wykreślanie od 1-go elementu

może jak się rozpatrzy kilka przypadków to wyjdzie

[Watari]

Wykreślamy zaczynając od drugiej osoby, czyli numerów parzystych.