Ο Φρίξος και ο πίνακας

[DrStrange]

Ο Φρίξος έχει ένα πίνακα με . Ξεκινά από το κελί (η αρίθμηση των στηλών και των γραμμών ξεκινά από το ) και θέλει να φτάσει στο κελί κινούμενος είτε προς τα πάνω είτε προς τα δεξιά ως εξής:
Αν την στιγμή που εξετάζουμε βρίσκεται στο μπορεί:
1. Να πάει στο πληρώνοντας νομίσματα.
2. Να πάει στο πληρώνοντας νομίσματα.
Θεωρήστε όλες τις δυνατές διαδρομές και μαζί τους το συνολικό κόστος της κάθε μιας. Πόσα και ποια δυνατά κόστη προκύπτουν? (συναρτήσει των )

[Mihalis_Lambrou]

Ο Φρίξος έχει ένα πίνακα με . Ξεκινά από το κελί (η αρίθμηση των στηλών και των γραμμών ξεκινά από το ) και θέλει να φτάσει στο κελί κινούμενος είτε προς τα πάνω είτε προς τα δεξιά ως εξής:
Αν την στιγμή που εξετάζουμε βρίσκεται στο μπορεί:
1. Να πάει στο πληρώνοντας νομίσματα.
2. Να πάει στο πληρώνοντας νομίσματα.
Θεωρήστε όλες τις δυνατές διαδρομές και μαζί τους το συνολικό κόστος της κάθε μιας. Πόσα και ποια δυνατά κόστη προκύπτουν? (συναρτήσει των )

Όλες οι διαδρομές έχουν κόστος . Η απόδειξη επαγωγικά: Για το άμεσο. Για το επαγωγικό βήμα, πάμε από το είτε

α) στο με κόστος όσο είχαμε πληρώσει μέχρι το συν άλλα . Σύνολο , όπως θέλαμε, είτε

β) στο με κόστος όσο είχαμε πληρώσει μέχρι το συν άλλα . Σύνολο , όπως θέλαμε.