Πέμπτη 16 Νοεμβρίου 2023

Ίππος σε κίνηση

Σε μια σκακιέρα, το κομμάτι του ίππου κινείται με έναν ιδιαίτερο τρόπο: είτε δύο κενά κάθετα και ένα οριζόντια, είτε δύο κενά οριζόντια και ένα κάθετα (δείτε την παρακάτω εικόνα). 
Στο πρόβλημά μας, έχουμε μια σκακιέρα στην παρακάτω μορφή (βλ.παρακάτω εικόνα). 
α) Μπορεί ο ίππος να ξεκινήσει από το τετράγωνο που φαίνεται και να ταξιδέψει γύρω από αυτή τη σκακιέρα, χρησιμοποιώντας τη γνωστή κίνηση του ίππου, περνώντας από κάθε τετράγωνο ακριβώς μία φορά και καταλήγοντας στο ίδιο τετράγωνο από το οποίο ξεκινά; 
β) Τι γίνεται αν ο ίππος ξεκινά από διαφορετικό τετράγωνο; 
Είναι πάντα δυνατό, μερικές φορές δυνατό ή ποτέ;

5 σχόλια:

  1. Ο γνωστός πιλότος/παγκ.πρωταθλητής της Φόρμουλα Ένα Χάμιλτον με διαβεβαίωσε ότι είναι πάντα δυνατόν.
    ΓΡ

    ΑπάντησηΔιαγραφή
  2. Ας θεωρήσουμε τη σκακιέρα ως ένα τετράγωνο πλέγμα 4Χ4, από το οποίο λείπουν οι 4 γωνίες
    Ας περιγράψουμε επίσης την θέση του ίππου με δύο συντεταγμένος (Χ,Υ), θεωρώντας ως θέση (1,1) την κάτω αριστερή γωνία. Στην εικόνα, η αρχική θέση του ίππου περιγράφεται ως (4,3). Το άθροισμα των δύο συντεταγμένων είναι 7 (περιττός αριθμός)
    Παρατηρούμε ότι η φύση της κίνησης του ίππου είναι τέτοια, ώστε σε κάθε κίνηση η μία συντεταγμένη του μεταβάλλεται κατά δύο θέσεις, και η δεύτερη κατά μία. Δηλαδή σε κάθε κίνηση του ίππου, το άθροισμα των συντεταγμένων του αλλάζει ισοτιμία (από περιττό σε άρτιο και αντίστροφα)
    Η συγκεκριμένη σκακιέρα έχει 12 τετράγωνα, εκ των οποίων τα 7 έχουν άρτιο άθροισμα συντεταγμένων και τα υπόλοιπα 5 περιττό. Επομένως, ο ίππος δεν μπορεί να περάσει από όλα τα τετράγωνα ακριβώς μία φορά πριν καταλήξει πάλι στο αρχικό τετράγωνο (εκτός αν επιτρέψουμε να κινηθεί και εκτός σκακιέρας)

    ΑπάντησηΔιαγραφή
  3. Στράτο, η σταυροειδής αυτή σκακιέρα είναι ένα Hamiltonian circuit.Το parity είναι σωστό καθώς ο ιπππς πάει πάντα από «λευκό» σε «μαύρο» και τούμπαλιν. Θεωρώντας κάθε κουτάκι κόμβο. Θα βοηθούσε να υπάρχουν συντεταγμενες ή αριθμημένα κουτάκια αλλά αφού δεν υπάρχουν …ονόμασε ας πούμε 1,2,3 ,…,12 τα κουτάκια με 1 εκεί που ξεκινάει ο ίππος , 2 δίπλα του , 3,4,5,6 η διπλανή στήλη (από πάνω προς τα κάτω) κλπ.
    Ένα knight tour είναι:
    1-9-3-11-5-7-12-4 -10 -2-8-6-1
    Γιώργος Ριζόπουλος

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Αν είχε άλλο ένα κουτάκι η σκακιέρα, δεν θα υπηρχε λύση

      Διαγραφή
  4. Για την διαδρομή του Ίππου, όρα εδώ: https://imgur.com/a/mhl2V8y

    ΑπάντησηΔιαγραφή