[DM 2005/08]

[1/08] (Modyfikacja problemu Wież Hanoi) Znajdź najkrótszą sekwencję ruchów przekładających wieżę n krążków z lewego pręta A na prawy pręt B, jeśli bezpośrednie ruchy między A i B są zabronione. Każdy ruch musi przenosić krążek "z" lub "na" pręt środkowy. Jak w klasycznym problemie w jednym ruchu przenosimy tylko jeden krążek oraz nie wolno umieścić większego krążka na mniejszym.

[2/08] Niektóre obszary określone przez n prostych na płaszczyźnie są nieskończone, podczas gdy inne są ograniczone. Jaka jest maksymalna liczba obszarów ograniczonych? Jaka jest maksymalna liczba obszarów nieograniczonych?

[3/08]* Spróbuj rozwiązać problem Wież Hanoi dla 4 prętów. Wyznacz oszacowania górne i dolne minimalnej liczby ruchów przekładających n krążków z lewego skrajnego pręta na prawy skrajny pręt z zachowaniem oryginalnych zasad (w jednym ruchu przenosimy tylko jeden krążek oraz nie wolno umieścić większego krążka na mniejszym). A może potrafisz skonstruować optymalny algorytm przekładania oraz dokładną wartość minimalnej liczby ruchów?

[4/08]* Danych jest n kul, z których każda waży 10 g., za wyjątkiem jednej, która waży 9 g. lub 11 g. Za pomocą k ważeń (na wadze szalkowej) należy rozstrzygnąć, która kula ma inną masę oraz czy jest ona lżejsza czy cięższa od pozostałych. Wyznacz, jaką maksymalną wartość może przyjmować n przy zadanym k jako funkcję f(k). Przedstaw algorytm ważenia dla dowolnego k i n = f(k).

[5/08] Rozwiąż zadanie [4/08] dla k = 3. Tzn. wyznacz maksymalną liczbę kul, dla których w 3 ważeniach zawsze można rozstrzygnąć, która z kul jest inna oraz czy jest cięższa czy lżejsza od pozostałych.

[6/08] Rozwiąż zadanie [5/08] przy założeniu, że nie trzeba odpowiedzieć czy wyjątkowa kula jest cięższa czy lżejsza, a jedynie odpowiedzieć, która z kul jest inna.

[7/08] Rozwiąż zadanie [5/08] przy założeniu, że wiadomo, że wyjątkowa kula jest cięższa.

[8/08] Na ile sposobów można pokryć prostokąt o wymiarach 2 x n nierozróżnialnymi prostokątami o wymiarach 2 x 1?

[9/08] Rozwiąż równanie rekurencyjne:

x₀ = 1;

x_n = x_n-1 + 2x_n-2 + ... + nx₀, dla n > 0.

[10/08] W pierwszym miesiącu mamy jednego królika - noworodka. Każdy królik w wieku co najmniej dwóch miesięcy rodzi dwa króliki w miesiącu. Króliki nie umierają. A zatem liczba królików w kolejnych miesiącach (zaczynając od pierwszego) będzie wynosić odpowiednio: 1, 1, 3, 5, 11, 21, ...

Wyznacz zwarty wzór na liczbę królików w n-tym miesiącu.

[11/08] Dany jest ciąg określony rekurencyjnie:

p₀ = 0

p_n = p_n-1 + 2ⁿn²

Wyznacz zwarty wzór na n-ty wyraz tego ciągu. (Wskazówka: zastosuj metodę zaburzania.)

---