Εκφώνηση:

Αφού η ομάδα ρομποτικής της Ευαγγελικής Σχολής κατέκτησε την πρώτη θέση στον διαγωνισμό CanSat in Greece (δείτε εδώ), άρχισε τις προετοιμασίες για το CanSat in Europe.
Τα παιδιά θέλουν να δοκιμάσουν την αντοχή του CanSat κάνοντας ένα πανέξυπνο πείραμα. Τα παιδιά έχουν στη διάθεσή τους ένα κτίριο με 100 ορόφους. Ξέρουν ότι το CanSat θα αντέξει την πτώση από τους πρώτους κάποιους ορόφους και θα σπάσει αν πέσει από τους υψηλότερους. Το σχέδιο τους είναι να πετάνε το CanSat από τους ορόφους μέχρι να βρουν τον υψηλότερο όροφο που δεν σπάει. Αν, κατά τη διάρκεια του πειράματος, το CanSat σπάσει, τότε δεν μπορούν να το ξαναχρησιμοποιήσουν. Επειδή όμως δεν θέλουν να ρισκάρουν την αποστολή τους, θα χρησιμοποιήσουν μόνο 2 παλαιότερα μοντέλα (με ίδια αντοχή), τα οποία δεν τους ενδιαφέρει αν καταστραφούν.
Επειδή η ομάδα έχει να κάνει ακόμα πολλές προετοιμασίες, τα παιδιά θέλουν να εξοικονομήσουν όσο περισσότερο χρόνο γίνεται. Θέλουν να κάνουν τις λιγότερες δυνατές πτώσεις για να βρούν τον υψηλότερο όροφο από τον οποίο δεν σπάει το CanSat. Μπορείς να τους βοηθήσεις;

Λύση:

Για λόγους ευκολίας θα λέμε έναν όροφο καλό άμα αφήσουμε το CanSat να πέσει από αυτόν και δεν σπάσει και κακό αλλιώς.
Ας λύσουμε πρώτα το ίδιο πρόβλημα αν τα παιδιά είχαν μόνο ένα διαθέσιμο CanSat. Εύκολα βλέπουμε ότι ο μόνος τρόπος για να βρουν τον υψηλότερο καλό όροφο με σιγουριά είναι να πετάνε το CanSat από όλους τους ορόφους με τη σειρά μέχρι να σπάσει. Άρα στη χειρότερη περίπτωση θα χρειαστούν 100 κινήσεις.
Ας επιστρέψουμε τώρα στο κανονικό πρόβλημα. Μπορούμε να υποθέσουμε ότι σε κάθε κίνηση τα παιδιά θα πετάνε το πρώτο CanSat από όλο και μεγαλύτερο ύψος μέχρι να σπάσει (αυτό είναι βέλτιστο γιατί αν ξέρουν ότι ένας όροφος είναι καλός, τότε είναι καλοί και όλοι οι από κάτω του και δεν έχει νόημα να τους ξαναδοκιμάσουν). Από τη στιγμή που το πρώτο CanSat σπάσει τα παιδιά είναι αναγκασμένα να δοκιμάσουν όλους τους ενδιάμεσους ορόφους (πάνω από τον τελευταίο καλό και κάτω από τον πρώτο κακό) για να βρούν ποιος από αυτούς είναι ο ζητούμενος (είδαμε πριν ότι αυτή είναι η μόνη στρατηγική που μπορούν να ακολουθήσουν αν έχουν μόνο ένα CanSat). Έστω ότι θέλουμε να βρούμε την απάντηση με κ κινήσεις. Τότε μας συμφέρει να αξιοποιήσουμε και τις κ κινήσεις σε κάθε πιθανή περίπτωση. Αρχικά θεωρούμε ότι ο τελευταίος καλός όρφος είναι ο 0ος και έχουμε κ κινήσεις. Θα δοκιμάσουμε τον όροφο 0+κ και αν είναι κακός αρκεί να ελέγξουμε κ-1 ορόφους ακόμα. Αν είναι καλός, τότε ο τελευταίος καλός όροφος είναι ο κ-οστός και έχουμε κ-1 κινήσεις. Συνεχίζοντας την ίδια διαδικασία θα ελέγξουμε τους ορφόφους κ+(κ-1), κ+(κ-1)+(κ-2), κτλ. Αρκεί επομένος να βρούμε τον ελάχιστο κ που ικανοποιεί την ανισότητα 1 + 2 + 3 + … + κ-1 + κ >= 100. Εύκολα βλέπουμε ότι η τελική απάντηση είναι κ = 14.
Μπορείτε να δείτε την λύση και εδώ.

–evpipis