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

#1

Συνέχεια αυτού και αυτού. Η δυσκολία ανεβαίνει αρκετά οπότε πάλι πάμε σε καινούργιο φάκελο.

Έστω φυσικοί αριθμοί k,n

με $k \leqslant n-2$ .

Στον πίνακα υπάρχουν γραμμένοι στην σειρά

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

μέχρι

) και ο Βασίλης επιλέγει είτε να προσθέσει σε όλους

είτε να αφαιρέσει από όλους

.

Σκοπός του Αντρέα είναι να κάνει τουλάχιστον n-k+2

από αυτούς τους αριθμούς (ταυτοχρόνως) πολλαπλάσια του

ενώ σκοπός του Βασίλη είναι να τον αποτρέψει.

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

#2

Βάζω μια λύση σε αυτήν την εξαιρετικά δύσκολη κατά την γνώμη μου άσκηση.

Η απάντηση είναι ότι κερδίζει ο Αντρέας.

Λήμμα 1: Έστω φυσικοί αριθμοί n,m

, έστω ότι έχουμε γραμμένους στον πίνακα τους αριθμούς $a_1,\ldots,a_n$ , και έστω r,s

μη αρνητικοί ακέραιοι. Τότε ο Αντρέας μπορεί να επιτύχει ένα από τα πιο κάτω
(α) Να αυξήσει τον a_1

κατά

.
(β) Να μειώσει τον a_1

κατά

.
(γ) Να κάνει τουλάχιστον n+2-r-s

από τους $a_2,\ldots,a_n$ πολλαπλάσια του

.

Ας παρατηρήσουμε ότι το Λήμμα 1 είναι αρκετό για να δείξουμε ότι ο Ανδρέας κερδίζει το παιγνίδι. Αν $a_1 \equiv a \bmod k$ , παίρνουμε m=k,r=k-a, s=a

οπότε από το Λήμμα 1 είτε κάνουμε τον a_1

πολλαπλάσιο του

, είτε κάνουμε τουλάχιστον n-k+2

από τους υπόλοιπους πολλαπλάσια του

. Στην δεύτερη περίπτωση ο Ανδρέας κερδίζει άμεσα. Στην πρώτη περίπτωση κερδίζει επαναλαμβάνοντας την διαδικασία επαγωγικά.

Η απόδειξη του Λήμματος 1 θα είναι με επαγωγή στο r+s

. Αν

και

είναι άμεσο αφού r=0

ή

και δεν έχουμε κάτι να δείξουμε. Για r+s=2

είναι επίσης άμεσο αφού αν $r \neq 0$ και $s \neq 0$ τότε r=1,s=1

και επιλέγοντας τον a_1

μπορούμε να πετύχουμε είτε το (α) είτε το (β).

Έστω λοιπόν ότι ο ισχυρισμός ισχύει για κάθε r,s

με $r+s = \ell$ . Θα δείξω ότι ισχύει και για κάθε r,s

με $r+s = \ell + 1$ . Έστω λοιπόν ότι $r+s = \ell + 1$

Από την επαγωγική υπόθεση ο Αντρέας μπορεί να επιτύχει ένα από τα πιο κάτω:
(α) Να αυξήσει τον a_1'

κατά

.
(β) Να μειώσει τον a_1'

κατά

.
(γ) Να κάνει τουλάχιστον n+2-r-s

από τους $a_2,\ldots,a_{n-1}$ πολλαπλάσια του

.

Προσοχή στο ότι μπορεί να πετύχει ένα από τα πιο πάνω χωρίς να πειράξει καθόλου τον a_n

.

Αν πετύχει το (β) ή (γ) τελειώσαμε. Οπότε μπορούμε να υποθέσουμε ότι πέτυχε το (α). Τώρα μπορεί να επιλέξει όλους τους αριθμούς $a_1,\ldots,a_n$ . Αν αυξηθούν όλοι κατά

, τότε ο

αυξήθηκε συνολικά κατά

και τελειώσαμε. Μπορούμε λοιπόν να υποθέσουμε ότι όλοι μειώθηκαν κατά

και πιο συγκεκριμένα μειώσαμε τον a_n

κατά

.

Έστω ότι με αυτήν την διαδικασία ο a_1

έγινε τώρα a_1' = a_1+t

. (Ασφαλώς είναι -s < t < r

.) Από την επαγωγική υπόθεση ο Αντρέας μπορεί να επιτύχει ένα από τα πιο κάτω:
(α) Να αυξήσει τον a_1

κατά

.
(β) Να μειώσει τον a_1

κατά

.
(γ) Να κάνει τουλάχιστον n+2-r-s

από τους $a_2,\ldots,a_{n-1}$ πολλαπλάσια του

.

Αν πετύχει τα (β),(γ) τότε τελειώσαμε ενώ αν πετύχει το (α) τότε στο επόμενο βήμα μπορεί να μειώσει τον a_n

κατά

.

Επαναλαμβάνοντας την διαδικασία όσες φορές χρειαστεί ο Αντρέας θα καταφέρει είτε να αυξήσει συνολικά τον a_1

κατά

, είτε να τον μειώσει κατά

είτε να κάνει τουλάχιστον n+2-r-s

από τους $a_2,\ldots,a_{n-1}$ πολλαπλάσια του

είτε να κάνει τον a_n

πολλαπλάσιο του

. Στις πρώτες τρεις περιπτώσεις το ζητούμενο αποδείχθηκε. Στην τελευταία περίπτωση το ζητούμενο έπεται επαγωγικά.

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

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

Re: Ξανά αριθμοί στον πίνακα

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