Αριθμοί στον πίνακα

[Demetres]

Αφορμή για αυτήν την άσκηση είναι ένα πολύ όμορφο και πολύ δύσκολο πρόβλημα το οποίο και θα ανεβάσω αργότερα. Εδώ βάζω μια ειδική και σαφώς πιο απλή περίπτωση

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

Σκοπός του Αντρέα είναι να κάνει τουλάχιστον από αυτούς τους αριθμούς (ταυτοχρόνως) πολλαπλάσια του ενώ σκοπός του Βασίλη είναι να τον αποτρέψει.

Ποιος από τους δύο έχει στρατηγική νίκης;

[taratoris]

Θα δείξουμε οτι ο Αντρέας έχει στρατηγική νίκης.

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

Αν ένα άκρο του πίνακα είναι ήδη πολλαπλάσιο του τότε έχουμε τελειώσει.

Διαφορετικά έχουμε δύο περιπτώσεις. Αν τα δύο άκρα είναι διαφορετικά τότε το ένα είναι ίσο με και το άλλο είναι ίσο με . Τότε ο Αντρέας διαλέγει όλα τα κελιά και ο Βασίλης είτε προσθέσει είτε αφαιρέσει θα έχει ως αποτέλεσμα ένα απο τα δύο κελιά στα άκρα να είναι πολλαπλάσιο του .

Τέλος εάν και τα δύο άκρα είναι ίσα τότε αρκεί ο Αντρέας να διαλέξει ένα απο τα δύο άκρα. Η κίνηση του Βασίλη είτε θα κάνει το άκρο αυτο πολλαπλάσιο του (οπότε τελειώσαμε) είτε θα το αλλάξει και θα έχουμε δύο διαφορετικά άκρα οπότε βρισκόμαστε στην άνω περίπτωση.

[Demetres]

Πολύ ωραία. Η συνέχεια εδώ. Μετά θα ακολουθήσει και η δύσκολη άσκηση.