Na ile różnych sposobów kangur może przeskoczyć patyki?

[Valiors]

Jest kangur, który może przeskoczyć 1, 2 lub 3 kamienie. Na ile różnych sposobów kangur może przeskoczyć przez 'n' kamieni? Bardzo proszę o podanie jak najprostszego rozwiązania.

[JakimPL]

To zadanie nie jest takie proste. Rozpatrzę jeden przypadek, w którym \(\displaystyle{ n = 3k}\). Udało mi się wykonkludować, iż liczbę przedstawień liczby \(\displaystyle{ 3k}\) na sumę liczb ze zbioru \(\displaystyle{ \{1,2,3\}}\), tj. liczby rozwiązań w zbiorze liczb nieujemnych równania:

\(\displaystyle{ a+2b+3c = 3k}\)

(liczbę przedstawień \(\displaystyle{ n}\) na sumę w ogólności ilustruje poniższa sekwencja:

Kod: Zaznacz cały

https://oeis.org/A001399

) da się wyrazić wzorem:

\(\displaystyle{ a_{k}=\frac{3 k^2}{4}+\frac{1}{8} \left(1-(-1)^k\right)}\)

Jeżeli kolejność jest ważna, to rozwiązanie dla \(\displaystyle{ n=3k}\) przedstawia poniższa sekwencja:

Kod: Zaznacz cały

https://oeis.org/A192806

Przykładowo, dla \(\displaystyle{ k=2}\):

\(\displaystyle{ \begin{array}{rcl|l} 6 & = & 1 + 1 + 1 + 1 + 1 + 1 & 1 \textrm{ permutacja}\\ & & 2 + 1 + 1 + 1 + 1 & 5 \textrm{ permutacji} \\ & & 2 + 2 + 1 + 1 & 6 \textrm{ permutacji} \\ & & 2 + 2 + 2 & 1 \textrm{ permutacja}\\ & & 3 + 1 + 1 + 1 & 4 \textrm{ permutacje}\\ & & 3 + 3 & 1 \textrm{ permutacja}\\ & & 3 + 2 + 1 & 6 \textrm{ permutacji}\end{array}}\)

stąd liczba możliwości to \(\displaystyle{ 24=1+5+6+1+4+1+6}\).

Rozwiązaniem ogólnym jest ciąg zwany ciągiem Tribonacciego i to sugeruje, w którym kierunku powinno podążać rozwiązanie .

[novy154]

A nie można prościej? Bo to jest chyba analogiczne do wchodzenia po schodach, kiedy możez pokonać odpowiednio jeden schodek, dwa i trzy.

No to:
niech \(\displaystyle{ a_{n}}\) będzie szukanym ciągiem
na n-ty schodek możesz wejść z:
a) schodka \(\displaystyle{ n-3}\), na który mogliśmy się dostać na \(\displaystyle{ a_{n-3}}\) sposobów
b) schodka \(\displaystyle{ n-2}\), na który analogicznie mogliśmy się dostać na \(\displaystyle{ a_{n-2}}\) sposobów
c) schodka poprzedniego, na ktory moglismy się dosta na \(\displaystyle{ a_{n-1}}\) sposobów

Zatem mamy wzór rekurencyjny \(\displaystyle{ a_{n} = a_{n-3} + a_{n-2} + a_{n-1}}\). Wystarczy wyznaczyć warunki początkowe. Jak ktoś chce wzór jawny, to można to równanie rozwiązać.

Gdzie jest błąd w tym rozumowaniu?

[JakimPL]

Można i tak byłoby najprościej.

Jak ktoś chce wzór jawny, to można to równanie rozwiązać.

To nie jest łatwe.