Soal Kombinatorik: Kemungkinan Menaiki Tangga

Berikut ini adalah soal kombinatorik, menghitung tangga.

Seorang anak menaiki 10 anak tangga. Dia hanya bisa melangkah satu satu atau melompati satu anak tangga. Berapa kemungkinan caranya menaiki tangga?

stair-2

Jumlah Anak Tangga: 1

Kemungkinan Langkah: 1

  1. Hanya ada satu langkah (1).

Jumlah Anak Tangga: 2

Kemungkinan Langkah: 2

  1. Melangkah satu-satu (1, 1).
  2. Melompat langsung (2).

Jumlah Anak Tangga: 3

Kemungkinan Langkah: 3

  1. Melangkah satu-satu (1, 1, 1)
  2. Dua lalu satu langkah (2, 1).
  3. Atau satu lalu dua langkah (1, 2).

Jumlah Anak Tangga: 4

Kemungkinan Langkah: 5

  1. Melangkah satu-satu (1, 1, 1, 1)
  2. Dua, satu, lalu satu langkah (2, 1, 1).
  3. Satu, dua, lalu satu langkah (1, 2, 1).
  4. Satu, satu, lalu dua langkah (1, 1, 2).
  5. Dua lalu dua langkah (2, 2).

Jumlah Anak Tangga: 5

Kemungkinan Langkah: 8

  1. Melangkah satu-satu (1, 1, 1, 1, 1)
  2. (2, 1, 1, 1).
  3. (1, 2, 1, 1)
  4. (1, 1, 2, 1)
  5. (1, 1, 1, 2)
  6. (2, 2, 1).
  7. (2, 1, 2).
  8. (1, 2, 2).

Pola Kemungkinan Langkah = Fibonaci

Perhatikan pola berikut:

  1. JumlahTangga(1) = 1
  2. JumlahTangga(2) = 2
  3. JumlahTangga(3) = 3
  4. JumlahTangga(4) = 5
  5. JumlahTangga(5) = 8

Kita bisa melihat bahwa 1, 2, 3, 5, 8, … membentuk pola fibonaci yang dimulai dari suku kedua.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ….

fib(1) = 1

fib(2)=2

fib(3)=fib(2)+fib(1)

fib(n)=fib(n-1)+fib(n-2)

  1. JumlahTangga(1) = fib(2) = 1
  2. JumlahTangga(2) = fib(3) = 2
  3. JumlahTangga(3) = fib(4) = 3
  4. JumlahTangga(4) = fib(5) = 5
  5. JumlahTangga(5) = fib(6) = 8
Maka, JumlahTangga(10) = fib(11) = 1

Pola Cara Melangkah

Untuk mencapai 5 anak tangga, kemungkinannya ada dua:

  1. Kita menginjak anak tangga ketiga, lalu melompat dua anak tangga ke anak tangga terakhir. Kemungkinan caranya sama dengan kemungkinan melangkah di 3 anak tangga.
  2. Kita menginjak anak tangga keempat, lalu satu langkah ke anak tanga terakhir. Kemungkinan caranya sama dengan kemungkinan melangkah di 4 anak tangga.

Maka, total kemungkinan 5 anak tangga adalah kemungkinan 3 anak tangga + 4 anak tangga.

Untuk mencapai 6 anak tangga, kemungkinannya ada dua:

  1. Kita menginjak anak tangga keempat, lalu melompat dua anak tangga ke anak tangga terakhir. Kemungkinan caranya sama dengan kemungkinan melangkah di 4 anak tangga.
  2. Kita menginjak anak tangga kelima, lalu satu langkah ke anak tanga terakhir. Kemungkinan caranya sama dengan kemungkinan melangkah di 5 anak tangga.

Maka, total kemungkinan 6 anak tangga adalah kemungkinan 4 anak tangga + 5 anak tangga.

Total kemungkinan 7 anak tangga adalah kemungkinan 5 anak tangga + 6 anak tangga.

Total kemungkinan 8 anak tangga adalah kemungkinan 6 anak tangga + 7 anak tangga.

Pola Umum

Misalkan \displaystyle P\left( n \right) adalah jumlah kemungkinan langkah untuk \displaystyle n anak tangga. Maka, berlaku:

\displaystyle P\left( n \right)=P\left( n-1 \right)+P\left( n-2 \right)

Jadi, secara berurutan:

\displaystyle \begin{array}{l}P\left( 1 \right)=1\\P\left( 2 \right)=2\\P\left( 3 \right)=2+1=3\\P\left( 4 \right)=3+2=5\\P\left( 5 \right)=5+3=8\\P\left( 6 \right)=8+5=13\end{array}

Maka, untuk 10 anak tangga ada 89 cara melangkah yang mungkin.

1, 3, 5, 8, 13, ….

Baca jawaban menariknya di mathforum.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s