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

[Διονύσιος Αδαμόπουλος]

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

[Demetres]

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

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

Θα προχωρήσουμε με επαγωγή στο . Οι περιπτώσεις είναι άμεσες. Έστω λοιπόν ότι μπορούμε να το πετύχουμε για και έστω ότι έχουμε τετραγωνάκια στην σειρά με το άθροισμα στα άσπρα να ισούται με το άθροισμα στα μαύρα. Προσθέτουμε ένα αρκετά μεγάλο αριθμό στα και ώστε ο αριθμός στο τετραγωνάκι να είναι μεγαλύτερος ή ίσος από τον αριθμό στο τετραγωνάκι . Τώρα μπορούμε να μηδενίσουμε τον αριθμό στο διατηρώντας τον αριθμό στο μη αρνητικό. Το άθροισμα στα άσπρα τετραγωνάκια εξακολουθεί να ισούται με το άθροισμα στα μαύρα τετραγωνάκια οπότε από την επαγωγική υπόθεση μπορούμε να επιτύχουμε τον μηδενισμό.

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

[Διονύσιος Αδαμόπουλος]

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

Το είχα βάλει εκεί γιατί είναι από την short list της ΙΜΟ 1989!

[Demetres]

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