Ο γρίφος της ημέρας – Οι Τρόποι (για καλούς λύτες)

...3

Πόσοι διαφορετικοί τρόποι υπάρχουν να φτάσουμε στην κορυφή μιας σκάλας που έχει 10 σκαλοπάτια εάν μπορούμε να ανέβουμε 1 ή 2 σκαλοπάτια τη φορά;

προτάθηκε από Carlo de Grandi
papaveri48.blogspot.com
degrand1@otenete.gr

3 σχόλια

  1. ΚΔ

    1 σκαλί με 1 τρόπο, 2 σκαλιά με 2 τρόπους. Για να ανέβω στο 3ο μπορώ από το 1ο με 1 τρόπο και από το 2ο με 2 τρόπους. Σύνολο 3 τρόποι. Για να ανέβω στο 4ο μπορώ από το 2ο με 2 τρόπους και από το 3ο με 3 τρόπους. Σύνολο 5 τρόποι. Όμοια για το 5ο 8 τρόπους, για το 6ο 13, για το 7ο 21, για το 8ο 34, για το 9ο 55 και για το 10ο 89.

  2. Θανάσης Παπαδημητρίου

    Αναδρομικά
    Έστω τ(ν) το πλήθος των τρόπων για να ανέβουμε στο σκαλοπάτι ν>2. Στο ν ανεβαίνουμε έχοντας πατήσει αμέσως πιο πριν είτε στο ν-1, είτε στο ν-2. Επομένως τ(ν)=τ(ν-1)+τ(ν-2) (Α)
    Έχουμε:
    τ(1)=1 (ένα μονό βήμα),
    τ(2)=2 (δύο μονά ή ένα διπλό βήμα)
    Με εφαρμογή της Α (fibonacci), έχουμε τ(3)=3, τ(4)=5 κλπ. και τελικά τ(10)=89

    Συνδυαστικά
    Μπορούμε να ανέβουμε τα 10 σκαλοπάτια σε 5 διπλά και 0 μονά βήματα ή σε 4 διπλά και 2 μονά ή σε 3 διπλά και 4 μονά ή σε 2 διπλά και 6 μονά ή σε 1 διπλό και 8 μονά ή σε 0 διπλά και 10 μονά. Έτσι έχουμε:
    C(5,5)+C(6,4)+C(7,3)+C(8,2)+C(9,1)+C(10,0) = 1+15+35+28+9+1 = 89

Απάντηση