Μηδενισμός σκακιέρας

Συντονιστές: Demetres, silouan

Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 676
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Μηδενισμός σκακιέρας

#1

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τρί Απρ 18, 2017 1:47 am

Σε κάθε τετράγωνο μιας m \times n σκακιέρας υπάρχει από ένας θετικός ακέραιος. Σε κάθε βήμα μπορούμε να προσθέτουμε έναν ακέραιο k σε κάθε ένα από δύο γειτονικούς αριθμούς έτσι ώστε να μην προκύπτει αρνητικός αριθμός (γειτονικοί αριθμοί είναι αυτοί που βρίσκονται σε τετράγωνα που έχουν μια κοινή πλευρά). Να βρείτε μια ικανή και αναγκαία συνθήκη ώστε να είναι δυνατός ο μηδενισμός όλων των αριθμών της σκακιέρας σε πεπερασμένο αριθμό βημάτων.


Houston, we have a problem!

Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7782
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Μηδενισμός σκακιέρας

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Απρ 18, 2017 9:15 pm

Θα δείξουμε ότι μπορούμε να μηδενίσουμε την σκακιέρα αν και μόνο αν το άθροισμα των αριθμών στα άσπρα τετραγωνάκια ισούται με το άθροισμα των αριθμών στα μαύρα τετραγωνάκια.

Η συνθήκη είναι προφανώς αναγκαία αφού η διαφορά των αθροισμάτων είναι αναλλοίωτη. Μένει να δείξουμε ότι είναι και ικανή. Θα δείξουμε μάλιστα ότι μπορούμε να το πετύχουμε ακόμη και αν έχουμε N τετραγωνάκια στην σειρά τα οποία είναι εναλλάξ άσπρα/μαύρα. (Είναι εύκολο να βάλουμε τα τετραγωνάκια της σκακιέρας σε τέτοια σειρά.)

Θα προχωρήσουμε με επαγωγή στο N. Οι περιπτώσεις N=1,2 είναι άμεσες. Έστω λοιπόν ότι μπορούμε να το πετύχουμε για N=k \geqslant 2 και έστω ότι έχουμε k+1 τετραγωνάκια στην σειρά με το άθροισμα στα άσπρα να ισούται με το άθροισμα στα μαύρα. Προσθέτουμε ένα αρκετά μεγάλο αριθμό στα k-1 και k ώστε ο αριθμός στο τετραγωνάκι k να είναι μεγαλύτερος ή ίσος από τον αριθμό στο τετραγωνάκι k+1. Τώρα μπορούμε να μηδενίσουμε τον αριθμό στο k+1 διατηρώντας τον αριθμό στο k μη αρνητικό. Το άθροισμα στα άσπρα τετραγωνάκια εξακολουθεί να ισούται με το άθροισμα στα μαύρα τετραγωνάκια οπότε από την επαγωγική υπόθεση μπορούμε να επιτύχουμε τον μηδενισμό.

Το μετέφερα στο Επίπεδο Αρχιμήδη μιας και δεν είναι ιδιαίτερα δύσκολο για να βρίσκεται στο Προχωρημένο Επίπεδο.


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 676
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Μηδενισμός σκακιέρας

#3

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τετ Απρ 19, 2017 12:22 am

Demetres έγραψε: Το μετέφερα στο Επίπεδο Αρχιμήδη μιας και δεν είναι ιδιαίτερα δύσκολο για να βρίσκεται στο Προχωρημένο Επίπεδο.
Το είχα βάλει εκεί γιατί είναι από την short list της ΙΜΟ 1989!


Houston, we have a problem!
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7782
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Μηδενισμός σκακιέρας

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Απρ 19, 2017 11:06 am

Κατανοητό. Τότε όμως οι διαγωνισμοί ήταν πιο εύκολοι. ;)


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης