Apabila Listi hanya dapat melakukan loncatan dengan panjang 7 atau 9, berikan salah satu cara ia dapat mencapai titik 72. Berikan sebagai urutan loncatan yang harus ia lakukan.

Apabila Listi hanya dapat melakukan loncatan dengan panjang 7 atau 9, ada berapa cara berbeda yang dapat ia lakukan untuk mencapai titik 72?

Apabila Listi dapat melakukan loncatan dengan panjang 1 atau 2 saja, ada berapa cara berbeda yang dapat ia lakukan untuk mencapai titik 12?

Apabila Listi hanya dapat melakukan loncatan yang panjangnya adalah angka pangkat 1, 2, 4, 8, 16, 32, dan 64, berikan salah satu cara untuk mencapai titik 100 yang menggunakan jumlah loncatan sesedikit mungkin.

Listi berada di titik 1, untuk sampai titik 72 listi perlu 71 titik.
Misalkan ingin memprioritaskan loncatan dengan panjang 7:
71 mod 7 = 1, dengan urutan 7-7-7-7-7-7-7-7-7-7
7 dan 9 memiliki selisih 2, sedangkan hasil mod adalah 1, sehingga perlu untuk mengurangi 7 dari daftar tadi menjadi:
7-7-7-7-7-7-7-7-7 dan bersisa 8.
8/2 = 4, sehingga kita dapat mengubah 7 menjadi 9 sebanyak 4.

Dengan demikian salah satu penyelesaiannya adalah 7-7-7-7-7-9-9-9-9.

Persoalan juga dapat dilakukan dengan rekursi, yaitu urutan dari posisi terakhir ke titik 1.
Listi dapat meloncat sepanjang 7 atau 9 yang mana membuatnya berada di posisi (x-7) atau (x-9). Jika posisinya sekarang adalah titik 8, maka ia hanya bisa meloncat dengan panjang 7 ke titik 1. Begitu pula jika ia berada di titik 10, ia hanya bisa meloncat dengan panjang 9 ke titik 1.

Misalkan f(x) merupakan banyaknya cara ia meloncat dari titik x ke titik 1 dengan panjang 7 atau 9. Maka f(72) = f(72-7) + f(72-9) dan seterusnya.
f(72) = f(65) + f(63)
f(65) = f(58) + f(56)
f(63) = f(56) + f(54)
f(58) = f(51) + f(49)
f(56) = f(49) + f(47)
f(54) = f(47) + f(45)
f(51) = f(44) + f(42)
f(49) = f(42) + f(40)
f(47) = f(40) + f(38)
f(45) = f(38) + f(36)
f(44) = f(37) + f(35)
f(42) = f(35) + f(33)
f(40) = f(33) + f(31)
f(38) = f(31) + f(29)
f(37) = f(30) + f(28)
f(36) = f(29) + f(27)
f(35) = f(28) + f(26)
f(33) = f(26) + f(24)
f(31) = f(24) + f(22)
f(30) = f(23) + f(21)
f(29) = f(22) + f(20)
f(28) = f(21) + f(19)
f(27) = f(20) + f(18)
f(26) = f(19) + f(17)
f(24) = f(17) + f(15)
f(23) = f(16) + f(14)
f(22) = f(15) + f(13)
f(21) = f(14) + f(12)
f(20) = f(13) + f(11)
f(19) = f(12) + f(10)
f(18) = f(11) + f(9)
f(17) = f(10) + f(8)
f(16) = f(9) + f(7)
f(15) = f(8) + f(6)
f(14) = f(7) + f(5)
f(13) = f(6) + f(4)
f(12) = f(5) + f(3)
f(11) = f(4) + f(2)
f(10) = 1
f(9) = f(2) + f(0)
f(8) = 1

Ketika Listi berada di titik 8 atau 10, ia hanya memiliki 1 cara saja. Sedangkan selain itu ia tidak mungkin lagi mencapai titik 1. Dengan demikian:
f(8) = 1
f(9) = 0 + 0 = 0
f(10) = 1
f(11) = 0 + 0 = 0
f(12) = 0 + 0 = 0
f(13) = 0 + 0 = 0
f(14) = 0 + 0 = 0
f(15) = 1 + 0 = 1
f(16) = 0 + 0 = 0
f(17) = 1 + 1 = 2
f(18) = 0 + 0 = 0
f(19) = 0 + 1 = 1
f(20) = 0 + 0 = 0
f(21) = 0 + 0 = 0
f(22) = 1 + 0 = 1
f(23) = 0 + 0 = 0
f(24) = 2 + 1 = 3
f(26) = 1 + 2 = 3
f(27) = 0 + 0 = 0
f(28) = 0 + 1 = 1
f(29) = 1 + 0 = 1
f(30) = 0 + 0 = 0
f(31) = 3 + 1 = 4
f(33) = 3 + 3 = 6
f(35) = 1 + 3 = 4
f(36) = 1 + 0 = 1
f(37) = 0 + 1 = 1
f(38) = 4 + 1 = 5
f(40) = 6 + 4 = 10
f(42) = 4 + 6 = 10
f(44) = 1 + 4 = 5
f(45) = 5 + 1 = 6
f(47) = 10 + 5 = 15
f(49) = 10 + 10 = 20
f(51) = 5 + 10 = 15
f(54) = 15 + 6 = 21
f(56) = 20 + 15 = 35
f(58) = 15 + 20 = 35
f(63) = 35 + 21 = 56
f(65) = 35 + 35 = 70
f(72) = 70 + 56 = 126

Dengan demikian, jika ia berada di titik 72 ia memiliki 126 cara.

Jika berada di titik 12:
f(12) = f(11) + f(10)
f(11) = f(10) + f(9)
f(10) = f(9) + f(8)…
dan terlihat pola fungsi fibonacci f(n) = f(n-1) + f(n-2), dengan f(0) dan f(1) = 0 (karena ada 0 cara untuk sampai titik 1 dari titik 1), dengan kata lain ia tidak bisa berpindah 1 maupun 2. Jika n = 2, ia hanya bisa berpindah ke titik 1, sedangkan jika n = 3 ia bisa berpindah ke titik 1 ataupun titik 2 (terdapat 2 cara).

Sehingga pola bilangan jika dimulai dari titik 2:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.
Jadi jika ia berada di titik 12, ia dapat menuju titik 1 dengan 144 cara.

Penyelesaian dapat dilakukan dengan melakukan konversi ke bilangan biner karena loncatan hanya merupakan bilangan kelipatan 2. Bilangan biner dari 100 adalah 1100100. Bit 1 terdapat pada 64, 32 dan 4, sehingga salah satu cara agar ia sampai dengan jumlah loncatan sedikit adalah 64, 32, 4.