Προβληματάκι
από Ρώσικο διαγωνισμό μαθηματικών
Έστω ότι έχουμε ένα λαβύρινθο σε σχήμα τετραγώνου
με 64 τετραγωνικά κελιά ,κάθε κελί έχει ένα βέλος που δείχνει είτε πάνω είτε κάτω
είτε αριστερά είτε δεξιά.
Το κελί που βρίσκεται πάνω δεξιά είναι αυτό
που οδηγεί στην έξοδο του λαβύρινθου. Έστω ότι κάποιος εξερευνητής ξεκινά από το κελί κάτω αριστερά και κινείται με τους εξής κανόνες. Μπορεί να μετακινηθεί μόνο σε γειτονικό κελί πάντα κατά την φορά που δείχνει το βέλος ,μόλις το κάνει το βέλος περιστρέφεται κατά 90ο με την φορά των δεικτών του ρολογιού. Αν δεν
είναι δυνατή η κίνηση του εξερευνητή γιατί το βέλος δείχνει εκτός του λαβύρινθου τότε παραμένει στο
κελί και το βέλος περιστρέφεται κατά 90ο με την φορά των δεικτών του
ρολογιού και τότε αν μπορεί κινείται, διαφορετικά επαναλαμβάνεται η διαδικασία
μέχρι να μπορεί να μεταβεί σε γειτονικό
κελί. Να αποδειχτεί ότι μετά από κάποιο αριθμό κινήσεων είναι βέβαιο ότι θα φτάσει
στο κελί της εξόδου και θα βγεί από τον λαβύρινθο.
Η λύση στα σχόλια
ΑπάντησηΔιαγραφήΛύση
Με απαγωγή σε άτοπο, Έστω ότι δεν πρόκειται να βγει ποτέ και θα περιπλανιέται επ άπειρο στον λαβύρινθο. Εφόσον ο λαβύρινθος έχει πεπερασμένο πλήθος κελιών αυτό σημαίνει ότι θα περάσει από τουλάχιστον ένα κελί άπειρες φορές και επειδή το βέλος στο κελί αυτό θα περιστρέφεται κάθε φορά που περνά θα επισκεφτεί και όλα τα γειτονικά του κελιά άπειρες φορές. Όμως με το ίδιο σκεπτικό για τα γειτονικά κελιά και τα δικά τους γειτονικά κελιά κατ επέκταση, αντιλαμβανόμαστε ότι θα περάσει από όλα τα κελιά του λαβύρινθου άπειρες φορές. Στα κελιά αυτά όμως συμπεριλαμβάνεται και το κελί της εξόδου πάνω δεξιά και σίγουρα κάποια στιγμή το βέλος θα δείξει την έξοδο.