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

#1

Συνέχεια από εδώ. Λίγο πιο δύσκολο γι' αυτό και σε διαφορετικό φάκελο.

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

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

μέχρι

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

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

.

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

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

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

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

taratoris · #2

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

Για κάθε πίνακα

μήκους $n \geq 3$ ο Αντρέας μπορεί να διαλέξει κινήσεις ώστε να δημιουργήσει σίγουρα ένα απο τα

παρακάτω ενδεχόμενα:

(i) Ενδεχόμενο πρώτο: Τουλάχιστον ένα απο τα δύο άκρα του πίνακα είναι πολλαπλάσιο του

.
(ii) Ενδεχόμενο δεύτερο: Όλα τα στοιχεία εκτός των δύο άκρων του πίνακα είναι πολλαπλάσια του

.

Βλέπουμε εύκολα οτι τότε συνεπάγεται οτι για κάθε πίνακα μήκους $n \geq 3$ , είναι πάντα εφικτό για τον Αντρέα να κάνει όλα πλην

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

. Ο λόγος είναι ο εξής. Εάν ο Αντρέας δημιουργήσει το δεύτερο ενδεχόμενο τότε όλα τα στοιχεία εκτός ίσως τα δύο άκρα του πίνακα είναι πολλαπλάσια του

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

.

Για να αποτρέψει ο Βασίλης το πρώτο ενδεχόμενο, πρέπει να αποτρέψει την περίπτωση οπου το ένα άκρο του πίνακα ισούται με (1mod4)

και το δεύτερο με 3(mod4)

. Διαφορετικά ο Αντρέας μπορεί να διαλέξει τα κελιά [1:n]

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

θα θέσει ένα κελί στο άκρο ως πολλαπλάσιο του

και συνεπώς θα δημιουργήσει το πρώτο ενδεχόμενο που θέλει να αποτρέψει.

Θα δείξουμε οτι εάν ο Βασίλης προσπαθήσει να αποτρέψει το πρώτο ενδεχόμενο τότε ο Αντρέας μπορεί να τον υποχρεώσει να δημιουργήσει το δεύτερο ενδεχόμενο. Έστω a,b

οι τιμές στα δύο άκρα. Τότε $a,b \neq 0 (mod4)$ και $\{a,b\}\neq \{1,3\} (mod4)$ διαφορετικά θα είμαστε στο πρώτο ενδεχόμενο.

Λήμμα: Μπορούμε να κάνουμε κινήσεις ώστε ακριβώς ένα απο τα δύο άκρα να ισούται με 2(mod4)

χωρίς να αλλάξουμε τα ενδιάμεσα κελιά.

Απόδειξη: Εάν (a,b)=(1,1)

τότε ο Αντρέας διαλέγει το κελί

και ο Βασίλης πρέπει να προσθέσει

στο

διαφορετικά είμαστε στο πρώτο ενδεχόμενο. Όμοια ελέγχονται και οι άλλες περιπτώσεις.

Ας υποθέσουμε λοιπόν δίχως βλάβη της γενικότητας οτι (a,b)=(1,2)

(οι υπολοιπες περιπτώσεις λειτουργούν αντίστοιχα με αυτήν).

Ας γράψουμε τον πίνακα $A=[a=1,l_2,...,l_{n-1},b=2]$ όπου $l_i \in \{0,1,2,3\}$ . Τότε η εξής ακολουθία επαναλαμβάνεται l_2

φορές:

(i) Ο Αντρέας επιλέγει τα κελιά [2:n]

(ii) Ο Βασιλης αφαιρεί

απο όλα (διαφορετικά (a,b)=(1,3)

)

(iii) Ο Αντρέας επιλέγει το άκρο

(που τώρα ισούται με

)

(iv) Ο Βασιλης προσθέτει

(διαφορετικά b=0(mod4)

).

Συνεπώς μετά απο l_2

επαναλήψεις ο πίνακας έχει την μορφή $A=[a=1,0,l'_{3}...,l'_{n-1},b=2]$

Στην συνέχεια ο Αντρέας επαναλαμβάνει με τα κελιά [3:n]

, μετά με

κ.ο.κ μέχρι [n-1,n]

. Έτσι στο τέλος A=[a=1,0,0,...,0,0,b=2]

και συνεπώς δημιουργήσαμε το δεύτερο ενδεχόμενο.

#3

Πολύ ωραία. Η δική μου λύση είναι λίγο διαφορετική:

Λήμμα 1: Έστω $a_1,\ldots,a_n$ οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους a_1,a_n

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

είτε μπορώ να κάνω όλους τους υπόλοιπους ίσους $\mod 4$ .

Λήμμα 2: Έστω $a_1,\ldots,a_n$ οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους a_1,a_n

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

είτε μπορώ να κάνω όλους τους υπόλοιπους πολλαπλάσια του

.

Ασφαλώς αν δείξω το Λήμμα 2, τότε ο Αντρέας κερδίζει. (Είτε επαγωγικά όπως στην απόδειξη του Ταρατόρη αν συμβεί η πρώτη περίπτωση, είτε άμεσα αν συμβεί η δεύτερη.)

Για να δείξω ότι μπορώ να πάω από το Λήμμα 1 στο Λήμμα 2 αρκεί να δείξω ότι αν έχω τρεις αριθμούς b_1,b_2,b_3

τότε μπορώ να κάνω έναν από αυτούς πολλαπλάσιο του

. [Σκεφτόμαστε ότι ο b_1

αντιστοιχεί στον a_1

, ο

στους $a_2 \equiv \cdots \equiv a_{n-1}$ και ο b_3

στον

.]

Αυτό είναι σχετικά εύκολο. Αρχικά κάνω τους b_1,b_2

περιττούς και τον b_3

άρτιο. Μπορώ να υποθέσω ότι $b_3 \equiv 2 \bmod 4$ αφού αλλιώς τελείωσα. Αν $b_1 \not \equiv b_2 \bmod 4$ τότε ο ένας είναι ισότιμος με $1 \mod 4$ και ο άλλος με $3 \mod 4$ . Αν τώρα ο Αντρέας επιλέξει τους b_1,b_2

τότε ένας από αυτούς σίγουρα θα γίνει πολλαπλάσιο του

. Μπορούμε λοιπόν να υποθέσουμε ότι και οι δύο είναι ισότιμοι με $1 \mod 4$ . (Η άλλη περίπτωση είναι παρόμοια.) Επιλέγοντας τους b_2,b_3

για να μην γίνει ο b_2

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

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

και στους δύο αριθμούς. Τότε όμως έχουμε $b_1 \equiv 1 \bmod 4$ και $b_2 \equiv 3 \bmod 4$ οπότε αν ο Αντρέας επιλέξει τους b_1,b_2,b_3

ένας από τους b_1,b_3

θα γίνει πολλαπλάσιο του

.

Μένει να αποδείξουμε το Λήμμα 1. Θα δείξουμε επαγωγικά το εξής.

Λήμμα 3: Έστω $a_1,\ldots,a_n$ οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά) και έστω ότι $a_2 \equiv \cdots \equiv a_k \bmod 4$ για κάποιο $2 \leqslant k \leqslant n-2$ . Τότε είτε μπορώ να κάνω ένα από τους a_1,a_n

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

είτε μπορώ να πετύχω $a_2 \equiv \cdots \equiv a_{k+1} \bmod 4$ .

Απόδειξη: Ξεκινάω κάνοντας τους a_1

και

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

όπως προηγουμένως. Χωρίς βλάβη της γενικότητας έχω $a_1 \equiv a_4 \equiv 1 \bmod 4$ . Τώρα επιλέγω αν χρειαστεί τον $a_{k+1}$ ώστε να έχει διαφορετική αρτιότητα από τους $a_2,\ldots,a_k$ . Άρα $\bmod 4$ οι αριθμοί θα είναι μιας από τις δύο πιο κάτω μορφές

(α) $1,\underbrace{a,\ldots,a}_{k-1},a+1,\ast,\ldots,\ast,1$

ή

(β) $1,\underbrace{a,\ldots,a}_{k-1},a-1,\ast,\ldots,\ast,1$

Στην περίπτωση (α) επιλέγω τους $a_1,\ldots,a_k$ και είτε ο a_1

θα γίνει πολλαπλάσιο του

είτε θα έχω $a_2 \equiv \cdots \equiv a_{k+1} \bmod 4$ .

Στην περίπτωση (β) πάλι καταλήγω σε επιθυμητό αποτέλεσμα αν επιλέξω τους $a_{k+1},\ldots,a_n$ .

$\rule{500pt}{0.5pt}$

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

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

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

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

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

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