"Οι εξετάσεις φοβίζουν και τον καλύτερα προετοιμασμένο, γιατί ο μεγαλύτερος ανόητος μπορεί να ζητήσει περισσότερα απ'ό,τι μπορεί να απαντήσει ο μεγαλύτερος σοφός."
Charles Caleb Colton
Μια σκακιέρα μxν έχει λευκό το πάνω-αριστερά τετράγωνό της. Ξεκινώντας απ'αυτό το τετράγωνο ένα κομμάτι κινείται διαγώνια και όταν φτάσει σε κάποιο "όριο" ακολουθεί τη διαγώνιο (σαν έναν Αξιωματικό που κινείται συνεχώς).
Η διαδικασία κίνησης τερματίζεται όταν το κομμάτι φθάσει σε κάποιο γωνιακό τετράγωνο Στην εικόνα φαίνεται η κίνηση αυτή για την περίπτωση σκακιέρας 4x5. Για ποιες τιμές των μ και ν το κομμάτι θα περάσει από όλα τα λευκά τετράγωνα;
Η διαδικασία κίνησης τερματίζεται όταν το κομμάτι φθάσει σε κάποιο γωνιακό τετράγωνο Στην εικόνα φαίνεται η κίνηση αυτή για την περίπτωση σκακιέρας 4x5. Για ποιες τιμές των μ και ν το κομμάτι θα περάσει από όλα τα λευκά τετράγωνα;
Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΓια ν=μ+1, μ=2,3,4,... (3Χ2, 4Χ3, 5Χ4,...,(μ+1)Χμ και
ΑπάντησηΔιαγραφήγια ν=μ-1, μ=3,4,5,...(2Χ3, 3Χ4, 4Χ5,...(μ-1)Χμ
Οι παραπάνω σχέσεις των μ,ν δεν καλύπτουν όλες τις δυνατές περιπτώσεις. Υπάρχουν και άλλες τιμές των μ και ν.
ΔιαγραφήΜάλλον ορθότερο είναι να βρούμε για ποιες τιμές των μ και ν το κομμάτι δεν μπορεί να περάσει από όλα τα λευκά τετράγωνα και αυτό θα συμβεί όταν το κομμάτι (λευκός αξιωματικός) θα μπλοκαριστεί και δεν θα μπορεί να συνεχίσει μέχρι τέλους την κίνηση του. Αυτό θα συμβεί αν βρεθεί σε γωνιακό (λευκό) τετράγωνο κατά την κίνηση του (φυσικά όχι το τελευταίο).
ΑπάντησηΔιαγραφήΆρα δεν θα μπορέσει να περάσει από όλα τα λευκά τετράγωνα
σε σκακιέρες πχ
3χ3, 3χ5, 3χ7,...,3χ(3+2κ), κ=0,1,2,3,....
4χ4, 4χ7, 4χ10,...4χ(4+3κ), κ=0,1,2,3,...
...................................................
...................................................
νχ(ν+(ν-1)*κ), κ=0,1,2,3,......
με εξαίρεση του κανόνα αυτού τις σκακιέρες 2χν
και φυσικά και στις αντίστοιχες στην άλλη διεύθυνση
(ν+(ν-1)*κ)χν με εξαίρεση τις σκακιέρες νχ2.
Στις υπόλοιπες περιπτώσεις (φυσικά και των 2χν και νχ2) μπορεί, υποθέτω και ευελπιστώ!
Μια πλήρης λευκή διαδρομή δε θα ολοκληρωθεί μόνο στην περίπτωση που το κομμάτι κατά την κίνησή του βρεθεί σε γωνιακό λευκό τετράγωνο που δε θα είναι το τελευταίο.
ΑπάντησηΔιαγραφήΟι ευνοϊκές περιπτώσεις για την ολοκλήρωση της διαδρομής είναι οι εξής:
α) μ=1 και ν=1
β) μ=2 και ν>=2 ή ν=2 και μ>=2
γ) αν μ, ν >=3 τότε:
αν μ>ν, τότε μ διάφορο του ν+λ(ν-1) και
αν ν>μ, τότε ν διάφορο του μ+λ(μ-1),
με λ=0,1,2,3,...
Eυχαριστώ για τα σχόλια και το ενδιαφέρον για το δύσκολο αυτό πρόβλημα!
ΑπάντησηΔιαγραφήΗ ικανή και αναγκαία συνθήκη για να περάσει απ'όλα τα λ. τετράγωνα μιας σκακιέρας μ Χ ν είναι:
M.K.Δ (μ-1 ,ν-1)=1 ή μ=ν=1
(όπου Μ.Κ.Δ= μέγιστος κοινός διαιρέτης. Δηλαδή πρέπει τα μ-1 και ν-1 να είναι μεταξύ τους πρώτοι.)
Αφήνω την απόδειξη-προς το παρόν- σαν άσκηση για όποιον φίλο θέλει να ασχοληθεί.
ΥΓ.Nα προσθέσω μόνο μια χρήσιμη παρατήρηση (η οποία όμως και αυτή χρήζει απόδειξης, αν και φαίνεται διαισθητικά προφανής). Κάθε "πλήρης" διαδρομή (ας πούμε "πλήρη" τη διαδρομή που χτυπάει όλα τα λ. τετράγωνα και "μη πλήρη" όποια τερματίζεται πριν περάσει απ'όλα τα λ. τετράγωνα) δημιουργεί στα "εσωτερικά" τετράγωνα , αυτά δηλαδή που δεν είναι σε κάποιο όριο-πλευρά της σκακιέρας, έναν "σταυρό" Χ . Δηλαδή η πλήρης διαδρομή διασταυρώνει τον εαυτό της σ'αυτά τα τετράγωνα. Δείτε και το σχήμα για την περίπτωση 4Χ5.
Δεκτό, σωστό και ευχαριστώ!
ΑπάντησηΔιαγραφήΗ συνθήκη για τους ν και μ, όπως την όρισα,απαγορεύει μεν στους ν-1 και μ-1 να είναι ο ένας πολλαπλάσιος του άλλου, αλλά δεν αποκλείει τις περιπτώσεις που οι ν-1 και μ-1, χωρίς να είναι πολλαπλάσιοι μεταξύ τους, έχουν κοινό διαιρέτη διάφορο του 1 (π.χ. ν=5, μ=15), όπου επίσης δεν προκύπτει πλήρης λευκή διαδρομή.
ΛΥΣΗ του Γιάκομπ Χούμπερ (Αυστρία) (σε δική μου μετάφραση από τα γερμανικά. Σε παρενθέσεις κάποιες δικές μου διευκρινίσεις)
ΑπάντησηΔιαγραφήΙσχυρισμός: Το κομμάτι θα περάσει από όλα τα λευκά τετράγωνα εάν και μόνο εάν (Μ.K.Δ(m-1,n-1)=1 ή m=n=1)
Ονομάζω μια διαδρομή «πλήρη» εάν καλύπτει όλα τα λευκά τετράγωνα και «μη πλήρη» σε αντίθετη περίπτωση
Πρόταση(Λήμμα): Μια πλήρης διαδρομή διασταυρώνει τον εαυτό της σε κάθε εσωτερικό τετράγωνο (δηλαδή σε τετράγωνο που δεν εφάπτεται σε κάποιο όριο της σκακιέρας).
Απόδειξη Λήμματος: Ας υποθέσουμε ότι η πρόταση είναι ψευδής. Τότε υπάρχει κάποιο εσωτερικό τετράγωνο S_0 στο οποίο μια πλήρης διαδρομή δεν διασταυρώνει τον εαυτό της. Έτσι, στα διαγωνίως γειτονικά στο S_0 τετράγωνα η διαδρομή πρέπει να «τρέχει» παράλληλα με τη διαδρομή που περνάει από το
S_0. Σε διαφορετική περίπτωση, αυτά τα τετράγωνα θα ήταν απροσπέλαστα. Έστω S_1 το χαμηλότερο από αυτά τα διαγωνίως γειτνιάζοντα τετράγωνα. Αν το S_1 ήταν κάποιο οριακό (εφαπτόμενο στο περίγραμμα της σκακιέρας)τετράγωνο,
η διαδρομή θα έστριβε εκεί και θα διασταύρωνε τον εαυτό της στο S_0. Άρα το S_1 δεν είναι οριακό και ούτε η διαδρομή αυτοδιασταυρώνεται στο S_1. Επαναλαμβάνοντας αυτόν το συλλογισμό παράγεται μια άπειρη αλυσίδα(ακολουθία) τετραγώνων πάνω σε μια πεπερασμένη σκακιέρα.
Αυτό (το άτοπο δηλαδή) αποδεικνύει την πρόταση.
Οι τετριμμένες περιπτώσεις: (1,1), (1,2) und (2,1) είναι λύσεις.
Σε όλες αυτές τις περιπτώσεις ισχύει: (Μ.Κ.Δ(m-1,n-1)=1 ή m=n=1).
Σε αυτά που ακολουθούν έστω m και n ακέραιοι μεγαλύτεροι ή ίσοι με 2.
Ακολούθως θα μετρήσω τον αριθμό των βημάτων σε μια πλήρη διαδρομή. Χάριν ευκολίας συμπεριλαμβάνω στο μέτρημα το αρχικό (πάνω αριστερά τετράγωνο)ώς: Βήμα 0. Από το αρχικό Λήμμα προκύπτει ότι κάθε πλήρη διαδρομή έχει μήκος ,έστω L:
L = ceil(m*n/2) + ceil((m-2)*(n-2)/2) – 1
(Σημείωση Γ.Ρ: με ceil συμβολίζει τη συνάρτηση «ceiling» ή ceil(x)=[x] ό άλλος συνήθης συμβολισμός για τον μικρότερο ακέραιο >= x )
Aυτή απλοποιείται στις:
L = (m-1)*(n-1) Aν m ή n είναι άρτιοι
L = (m-1)*(n-1)+1 Αν m και n είναι περιττοί
Τώρα, συμβολίζω με p(l) το τετράγωνο που καταλήγει μετά από l Βήμα.
(Θυμίζω ότι: p(0) = (1,1))
Είναι εύκολο να διαπιστώσουμε ότι η διαδρομή καταλήγει στο άνω ή κάτω όριο εάν και μόνο εάν
(m-1)|l και στο αριστερό ή δεξί όριο ε.κ.μ.εάν (n-1)|l
Έτσι η διαδρομή τερματίζεται εάν και μόνο εάν l = Ε.Κ.Π((m-1)*(n-1))
Τώρα, αν ΜΚΔ((m-1)*(n-1)) = 1 η διαδρομή τερματίζεται μετά από
ΕΚΠ((m-1)*(n-1)) = L Βήματα και γι’αυτό είναι μια «πλήρης» διαδρομή.
Αν ΜΚΔ((m-1)*(n-1)) > 1 η διαδρομή θα τερματίσει μετά από
ΕΚΠ((m-1)*(n-1)) < L βήματα, και γι’αυτό είναι «μη πλήρης».
Αυτό αποδεικνύει ότι υπάρχει μια πλήρης διαδρομή εάν και μόνο εάν:
M.K.Δ((m-1)*(n-1)) = 1.