Σε μία μυθική χώρα υπάρχει κάποιος αριθμός από κάστρα και τρεις δρόμοι ξεκινούν από το κάθε κάστρο. Ένας ιππότης ξεκινάει από το κάστρο του για ένα μεγάλο ταξίδι σε όλη τη χώρα. Σε κάθε κάστρο που φτάνει διανυκτερεύει και την επόμενη ημέρα αφήνει το κάστρο πηγαίνοντας είτε δεξιά είτε αριστερά. Δεν παίρνει ποτέ το δρόμο από τον οποίο ήρθε στο κάστρο και δεν στρίβει ποτέ προς την ίδια κατεύθυνση, όπως έκανε προηγουμένως. Να αποδειχθεί ότι ο ιππότης θα φτάσει ξανά στο κάστρο του.
Φαντάζομαι ότι το πρόβλημα αναφέρεται σε κλειστό κύκλωμα κάστρων – δρόμων και ότι κάθε δρόμος από τους τρεις, που ξεκινάνε από ένα κάστρο, συνδέει αυτό το κάστρο με κάποιο άλλο κάστρο.
ΑπάντησηΔιαγραφή(Αυτό μπορεί να συμβεί για έναν ελάχιστο αριθμό 4 κάστρων και 6 δρόμων ή για οποιοδήποτε ζυγό αριθμό α (>4) κάστρων που συνδέονται με ένα δίκτυο α*3/2 δρόμων, π.χ. 6-9, 8-12, 10-15 κ.ο.κ.)
Εφόσον ο αριθμός κάστρων είναι πεπερασμένος, η περίπτωση που ο ιππότης δε θα έφτανε ξανά στο κάστρο του θα υπήρχε μόνο αν η κίνησή του εγκλωβιζόταν σε κάποια κλειστή εσωτερική διαδρομή (βραχυκύκλωμα).
Με δεδομένο ότι απαγορεύεται η κίνηση ‘μπρος-πίσω’, η ελάχιστη δυνατή κλειστή σύνδεση είναι μεταξύ 3 κάστρων, έστω Α, Β, Γ που συνδέονται με δρόμους ανά 2 μεταξύ τους. Αν ο ιππότης, φεύγοντας από ένα κάστρο Χ, φτάσει σε κάποιο από αυτά, έστω το Α, τότε με την έξοδό του από το Α θα ακολουθήσει αναγκαστικά διαδρομή ή Α->Β->Γ ή Α->Γ->Β. Με την έξοδό του όμως από το Γ ή το Β αντιστοίχως, δεν επιτρέπεται να επιστρέψει στο Α, γιατί αυτό θα απαιτούσε δύο συνεχόμενες στροφές δεξιά-δεξιά ή αριστερά-αριστερά, και επομένως θα συνεχίσει σε κάποιο επόμενο κάστρο Δ. Ομοίως, από το Δ δεν μπορεί να γυρίσει σε κάποιο από τα Β ή Γ και έτσι θα συνεχίσει σε κάποιο επόμενο κάστρο Ε κ.ο.κ.
Τα ίδια ισχύουν για πιθανές κλειστές συνδέσεις με περισσότερα από 3 κάστρα, συνδεόμενα ανά 2 διαδοχικά, καθώς ο ιππότης δεν μπορεί να κινηθεί κατά μήκος μιας κλειστής σύνδεσης για περισσότερα από 2 βήματα, χωρίς να παραβιάσει τον κανόνα ‘αριστερά-δεξιά’ ή το αντίθετο.
Επομένως δεν υπάρχει βραχυκύκλωμα, ο ιππότης δεν περνάει ποτέ παραπάνω από μία φορά από κάποιο κάστρο και κάποια στιγμή θα φτάσει ξανά στο αρχικό κάστρο του.