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

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

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

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

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Οκτ 12, 2016 11:34 am

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

Έστω φυσικοί αριθμοί k,n με k \leqslant n-2.

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

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

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



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

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

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Νοέμ 02, 2016 11:22 am

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

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

Λήμμα 1: Έστω φυσικοί αριθμοί n,m, έστω ότι έχουμε γραμμένους στον πίνακα τους αριθμούς a_1,\ldots,a_n, και έστω r,s μη αρνητικοί ακέραιοι. Τότε ο Αντρέας μπορεί να επιτύχει ένα από τα πιο κάτω
(α) Να αυξήσει τον a_1 κατά r.
(β) Να μειώσει τον a_1 κατά s.
(γ) Να κάνει τουλάχιστον n+2-r-s από τους a_2,\ldots,a_n πολλαπλάσια του m.

Ας παρατηρήσουμε ότι το Λήμμα 1 είναι αρκετό για να δείξουμε ότι ο Ανδρέας κερδίζει το παιγνίδι. Αν a_1 \equiv a \bmod k, παίρνουμε m=k,r=k-a, s=a οπότε από το Λήμμα 1 είτε κάνουμε τον a_1 πολλαπλάσιο του k, είτε κάνουμε τουλάχιστον n-k+2 από τους υπόλοιπους πολλαπλάσια του k. Στην δεύτερη περίπτωση ο Ανδρέας κερδίζει άμεσα. Στην πρώτη περίπτωση κερδίζει επαναλαμβάνοντας την διαδικασία επαγωγικά.

Η απόδειξη του Λήμματος 1 θα είναι με επαγωγή στο r+s. Αν r+s=0 και r+s=1 είναι άμεσο αφού r=0 ή s=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' κατά r-1.
(β) Να μειώσει τον a_1' κατά s.
(γ) Να κάνει τουλάχιστον n+2-r-s από τους a_2,\ldots,a_{n-1} πολλαπλάσια του m.

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

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

Έστω ότι με αυτήν την διαδικασία ο a_1 έγινε τώρα a_1' = a_1+t. (Ασφαλώς είναι -s < t < r.) Από την επαγωγική υπόθεση ο Αντρέας μπορεί να επιτύχει ένα από τα πιο κάτω:
(α) Να αυξήσει τον a_1 κατά r-t-1.
(β) Να μειώσει τον a_1 κατά s-t.
(γ) Να κάνει τουλάχιστον n+2-r-s από τους a_2,\ldots,a_{n-1} πολλαπλάσια του m.

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

Επαναλαμβάνοντας την διαδικασία όσες φορές χρειαστεί ο Αντρέας θα καταφέρει είτε να αυξήσει συνολικά τον a_1 κατά r, είτε να τον μειώσει κατά s είτε να κάνει τουλάχιστον n+2-r-s από τους a_2,\ldots,a_{n-1} πολλαπλάσια του m είτε να κάνει τον a_n πολλαπλάσιο του m. Στις πρώτες τρεις περιπτώσεις το ζητούμενο αποδείχθηκε. Στην τελευταία περίπτωση το ζητούμενο έπεται επαγωγικά.


Απάντηση

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

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

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