Farklı şekillerde merdiven çıkma mantık sorusu

İkinci katta oturuyorsunuz. Merdivenlerde dairenize kadar toplam 30 basamak var. Her adımda en fazla 3 basamak çıkabildiğinize göre, bu merdivenleri kaç farklı şekilde çıkabilirsiniz?

ÖR: Merdivenleri [1-1-1-1-1-...-1], [3-3-3-3-3-...-3], [1-2-3-2-1-...-2], ... şeklinde çıkabilirsiniz.

Farklı şekillerde merdiven çıkma mantık sorusunun cevabı

Oldukça zor görünen bu sorunun cevabı o kadar da zor değildir. Zorulara özyinelemeli olarak bakmayı öğrendiğinizce, bu tarz soruların cevaplarını kolaylıkla bulabilirsiniz. Özyinelemeli ifadesiyle kastımız, kendi içerisinde sürekli tekrar eden örüntülerin olmasıdır.

Neyse, teorik açıklamaları bir kenara bırakalım ve sorunun cevabına geçelim:

Merdivenleri çıkan kişi her adımında bir ya da iki ya da üç basamak birden atlayabiliyormuş. Başka bir ifadeyle, bulunduğu basamağa üç farklı şekilde gelebilir:

- Bir önceki basamaktan bir basamaklık bir adımla,
- İki önceki basamaktan iki basamaklık bir adımla,
- Üç önceki basamaktan üç basamaklık bir adımla.

Burada dikkat edilmesi gereken konu; iki önceki basamaktan birer basamaklık iki adımda gelinme durumunu düşünmeye gerek yoktur. ÇÜnkü, bu durum zaten bir önceki basamaktan gelme durumunun içinde sayılmaktadır.

Hemen ilk denemelerimizi yapalım. Birinci basamağa sadece tek şekilde gelinebilir (1). İkinci basamağa ise iki farklı şekilde gelinebilir (1-1, 2). Üçüncü basamağa ise dört farklı şekilde gelinebilir (1-1-1, 1-2, 2-1, 3).

Az önce açıkladığımız özyinelemeli çözümü uygularsak, dördüncü basamağa önceki farklı durumları kullanarak üç farklı şekilde ulaşılabilir: Bir önceki basamaktan bir basamaklık adımla, iki önceki basamaktan iki basmaklık adımla ya da üç önceki basamaktan üç basamakklık bir adımla. Toplam 1 + 2 + 4 = 7 farklı şekilde ulaşılabilir (1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2, 1-3, 3-1).

Doğru cevap: 53798080 farklı şekilde çıkılabilir.