Μηδενισμός σκακιέρας
Συντονιστές: Demetres, silouan
- Διονύσιος Αδαμόπουλος
- Δημοσιεύσεις: 807
- Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
- Τοποθεσία: Πύργος Ηλείας
Μηδενισμός σκακιέρας
Σε κάθε τετράγωνο μιας σκακιέρας υπάρχει από ένας θετικός ακέραιος. Σε κάθε βήμα μπορούμε να προσθέτουμε έναν ακέραιο σε κάθε ένα από δύο γειτονικούς αριθμούς έτσι ώστε να μην προκύπτει αρνητικός αριθμός (γειτονικοί αριθμοί είναι αυτοί που βρίσκονται σε τετράγωνα που έχουν μια κοινή πλευρά). Να βρείτε μια ικανή και αναγκαία συνθήκη ώστε να είναι δυνατός ο μηδενισμός όλων των αριθμών της σκακιέρας σε πεπερασμένο αριθμό βημάτων.
Houston, we have a problem!
Λέξεις Κλειδιά:
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Μηδενισμός σκακιέρας
Θα δείξουμε ότι μπορούμε να μηδενίσουμε την σκακιέρα αν και μόνο αν το άθροισμα των αριθμών στα άσπρα τετραγωνάκια ισούται με το άθροισμα των αριθμών στα μαύρα τετραγωνάκια.
Η συνθήκη είναι προφανώς αναγκαία αφού η διαφορά των αθροισμάτων είναι αναλλοίωτη. Μένει να δείξουμε ότι είναι και ικανή. Θα δείξουμε μάλιστα ότι μπορούμε να το πετύχουμε ακόμη και αν έχουμε τετραγωνάκια στην σειρά τα οποία είναι εναλλάξ άσπρα/μαύρα. (Είναι εύκολο να βάλουμε τα τετραγωνάκια της σκακιέρας σε τέτοια σειρά.)
Θα προχωρήσουμε με επαγωγή στο . Οι περιπτώσεις είναι άμεσες. Έστω λοιπόν ότι μπορούμε να το πετύχουμε για και έστω ότι έχουμε τετραγωνάκια στην σειρά με το άθροισμα στα άσπρα να ισούται με το άθροισμα στα μαύρα. Προσθέτουμε ένα αρκετά μεγάλο αριθμό στα και ώστε ο αριθμός στο τετραγωνάκι να είναι μεγαλύτερος ή ίσος από τον αριθμό στο τετραγωνάκι . Τώρα μπορούμε να μηδενίσουμε τον αριθμό στο διατηρώντας τον αριθμό στο μη αρνητικό. Το άθροισμα στα άσπρα τετραγωνάκια εξακολουθεί να ισούται με το άθροισμα στα μαύρα τετραγωνάκια οπότε από την επαγωγική υπόθεση μπορούμε να επιτύχουμε τον μηδενισμό.
Το μετέφερα στο Επίπεδο Αρχιμήδη μιας και δεν είναι ιδιαίτερα δύσκολο για να βρίσκεται στο Προχωρημένο Επίπεδο.
Η συνθήκη είναι προφανώς αναγκαία αφού η διαφορά των αθροισμάτων είναι αναλλοίωτη. Μένει να δείξουμε ότι είναι και ικανή. Θα δείξουμε μάλιστα ότι μπορούμε να το πετύχουμε ακόμη και αν έχουμε τετραγωνάκια στην σειρά τα οποία είναι εναλλάξ άσπρα/μαύρα. (Είναι εύκολο να βάλουμε τα τετραγωνάκια της σκακιέρας σε τέτοια σειρά.)
Θα προχωρήσουμε με επαγωγή στο . Οι περιπτώσεις είναι άμεσες. Έστω λοιπόν ότι μπορούμε να το πετύχουμε για και έστω ότι έχουμε τετραγωνάκια στην σειρά με το άθροισμα στα άσπρα να ισούται με το άθροισμα στα μαύρα. Προσθέτουμε ένα αρκετά μεγάλο αριθμό στα και ώστε ο αριθμός στο τετραγωνάκι να είναι μεγαλύτερος ή ίσος από τον αριθμό στο τετραγωνάκι . Τώρα μπορούμε να μηδενίσουμε τον αριθμό στο διατηρώντας τον αριθμό στο μη αρνητικό. Το άθροισμα στα άσπρα τετραγωνάκια εξακολουθεί να ισούται με το άθροισμα στα μαύρα τετραγωνάκια οπότε από την επαγωγική υπόθεση μπορούμε να επιτύχουμε τον μηδενισμό.
Το μετέφερα στο Επίπεδο Αρχιμήδη μιας και δεν είναι ιδιαίτερα δύσκολο για να βρίσκεται στο Προχωρημένο Επίπεδο.
- Διονύσιος Αδαμόπουλος
- Δημοσιεύσεις: 807
- Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
- Τοποθεσία: Πύργος Ηλείας
Re: Μηδενισμός σκακιέρας
Το είχα βάλει εκεί γιατί είναι από την short list της ΙΜΟ 1989!Demetres έγραψε: Το μετέφερα στο Επίπεδο Αρχιμήδη μιας και δεν είναι ιδιαίτερα δύσκολο για να βρίσκεται στο Προχωρημένο Επίπεδο.
Houston, we have a problem!
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 8 επισκέπτες