.svg.png)
Θεωρούμε τα \(50\) αστέρια της αμερικανικής σημαίας, τα οποία αντιστοιχούν στις \(50\) πολιτείες των Ηνωμένων Πολιτειών.
Ένας σκίουρος θέλει να πραγματοποιήσει μια κυκλική διαδρομή περνώντας από όλα τα αστέρια με μια ακολουθία αλμάτων.
Αυτό σημαίνει ότι:
- επισκέπτεται κάθε αστέρι ακριβώς μία φορά,
- και στο τέλος επιστρέφει στο αρχικό αστέρι.
Σε κάθε άλμα επιτρέπεται να μετακινείται σε αστέρι που βρίσκεται:
- οριζόντια γειτονικά,
- κατακόρυφα γειτονικά,
- ή διαγώνια γειτονικά
ως προς το αστέρι στο οποίο βρίσκεται εκείνη τη στιγμή.
Να βρεθούν:
- ο ελάχιστος δυνατός αριθμός διαγώνιων αλμάτων,
- και ο ελάχιστος δυνατός αριθμός μη διαγώνιων αλμάτων.
EisatoponAI
Your Daily Experience of Math Adventures
Combinatorics • Graph Theory • Mathematical Puzzles
Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ
PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify
📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα
Δες τα βιβλία →
1 σχόλιο:
Ας θεωρήσουμε τη γνωστή διάταξη των 50 αστεριών της αμερικανικής σημαίας:
ΑπάντησηΔιαγραφή• 9 σειρές,
• εναλλάξ με 6 και 5 αστέρια.
Ο σκίουρος πρέπει να κάνει έναν Χαμιλτονιανό κύκλο:
να περάσει από κάθε αστέρι ακριβώς μία φορά και να επιστρέψει στην αρχή.
1. Ελάχιστος αριθμός διαγώνιων αλμάτων
Τα αστέρια κάθε σειράς συνδέονται οριζόντια μεταξύ τους.
Για να περάσει όμως ο σκίουρος από μια σειρά στην επόμενη, είναι αναγκασμένος να χρησιμοποιήσει διαγώνιο άλμα.
Υπάρχουν συνολικά:
• 9 σειρές,
• άρα 8 «σύνορα» μεταξύ διαδοχικών σειρών.
Σε έναν κλειστό κύκλο, κάθε τέτοιο σύνορο πρέπει να διασχίζεται άρτιο αριθμό φορές· τουλάχιστον 2 φορές, αλλιώς ο κύκλος δεν μπορεί να επιστρέψει.
Άρα απαιτούνται τουλάχιστον
2×8=16 διαγώνια άλματα.
Και πράγματι υπάρχει διαδρομή που χρησιμοποιεί ακριβώς 16 διαγώνια άλματα (και όλα τα υπόλοιπα οριζόντια).
Άρα:
16 είναι ο ελάχιστος δυνατός αριθμός διαγώνιων αλμάτων.
2. Ελάχιστος αριθμός μη διαγώνιων αλμάτων
Ο συνολικός αριθμός αλμάτων σε έναν τέλειο κύκλο είναι πάντα 50
(ένα για κάθε μετάβαση μεταξύ διαδοχικών αστεριών).
Αφού υπάρχει κυκλική διαδρομή που χρησιμοποιεί μόνο διαγώνια άλματα, ο αριθμός των μη διαγώνιων αλμάτων μπορεί να γίνει μηδέν.
Άρα:
0 είναι ο ελάχιστος δυνατός αριθμός μη διαγώνιων αλμάτων.
Τελική απάντηση
• Ελάχιστος αριθμός διαγώνιων αλμάτων: 16
• Ελάχιστος αριθμός μη διαγώνιων αλμάτων: 0