Πάλι αριθμοί στον πίνακα
Συντονιστές: cretanman, silouan, rek2
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Πάλι αριθμοί στον πίνακα
Συνέχεια από εδώ. Λίγο πιο δύσκολο γι' αυτό και σε διαφορετικό φάκελο.
Στον πίνακα υπάρχουν γραμμένοι στην σειρά ακέραιοι αριθμοί. Σε κάθε βήμα ο Ανδρέας διαλέγει κάποιους συνεχόμενους αριθμούς (από μέχρι ) και ο Βασίλης επιλέγει είτε να προσθέσει σε όλους είτε να αφαιρέσει από όλους .
Σκοπός του Αντρέα είναι να κάνει τουλάχιστον από αυτούς τους αριθμούς (ταυτοχρόνως) πολλαπλάσια του ενώ σκοπός του Βασίλη είναι να τον αποτρέψει.
Ποιος από τους δύο έχει στρατηγική νίκης;
Στον πίνακα υπάρχουν γραμμένοι στην σειρά ακέραιοι αριθμοί. Σε κάθε βήμα ο Ανδρέας διαλέγει κάποιους συνεχόμενους αριθμούς (από μέχρι ) και ο Βασίλης επιλέγει είτε να προσθέσει σε όλους είτε να αφαιρέσει από όλους .
Σκοπός του Αντρέα είναι να κάνει τουλάχιστον από αυτούς τους αριθμούς (ταυτοχρόνως) πολλαπλάσια του ενώ σκοπός του Βασίλη είναι να τον αποτρέψει.
Ποιος από τους δύο έχει στρατηγική νίκης;
Λέξεις Κλειδιά:
Re: Πάλι αριθμοί στον πίνακα
Θα δείξουμε οτι πάλι ο Αντρέας έχει στατηγική νίκης. Θα αποδείξουμε την εξής πρόταση:
Για κάθε πίνακα μήκους ο Αντρέας μπορεί να διαλέξει κινήσεις ώστε να δημιουργήσει σίγουρα ένα απο τα παρακάτω ενδεχόμενα:
(i) Ενδεχόμενο πρώτο: Τουλάχιστον ένα απο τα δύο άκρα του πίνακα είναι πολλαπλάσιο του .
(ii) Ενδεχόμενο δεύτερο: Όλα τα στοιχεία εκτός των δύο άκρων του πίνακα είναι πολλαπλάσια του .
Βλέπουμε εύκολα οτι τότε συνεπάγεται οτι για κάθε πίνακα μήκους , είναι πάντα εφικτό για τον Αντρέα να κάνει όλα πλην απο τα κελιά του πολλαπλάσια του . Ο λόγος είναι ο εξής. Εάν ο Αντρέας δημιουργήσει το δεύτερο ενδεχόμενο τότε όλα τα στοιχεία εκτός ίσως τα δύο άκρα του πίνακα είναι πολλαπλάσια του . Αντιθέτως, εάν πραγματοποιήσει το πρώτο ενδεχόμενο τότε μπορεί να προχωρήσει επαγωγικά στον πίνακα που αποτελείται απο όλα τα κελιά του αρχικού πλην του άκρου που έχει γίνει πολλαπλάσιο του .
Για να αποτρέψει ο Βασίλης το πρώτο ενδεχόμενο, πρέπει να αποτρέψει την περίπτωση οπου το ένα άκρο του πίνακα ισούται με και το δεύτερο με . Διαφορετικά ο Αντρέας μπορεί να διαλέξει τα κελιά (θα χρησιμοποιήσω αυτόν τον συμβολισμό για να συμβολίσω οτι ο Αντρέας επέλεξε τα κελιά ανάμεσα και συμπεριλαμβανομένων του πρώτου και του n-οστού.) Τότε είτε ο Βασίλης προσθέσει είτε αφαιρέσει θα θέσει ένα κελί στο άκρο ως πολλαπλάσιο του και συνεπώς θα δημιουργήσει το πρώτο ενδεχόμενο που θέλει να αποτρέψει.
Θα δείξουμε οτι εάν ο Βασίλης προσπαθήσει να αποτρέψει το πρώτο ενδεχόμενο τότε ο Αντρέας μπορεί να τον υποχρεώσει να δημιουργήσει το δεύτερο ενδεχόμενο. Έστω οι τιμές στα δύο άκρα. Τότε και διαφορετικά θα είμαστε στο πρώτο ενδεχόμενο.
Λήμμα: Μπορούμε να κάνουμε κινήσεις ώστε ακριβώς ένα απο τα δύο άκρα να ισούται με χωρίς να αλλάξουμε τα ενδιάμεσα κελιά.
Απόδειξη: Εάν τότε ο Αντρέας διαλέγει το κελί και ο Βασίλης πρέπει να προσθέσει στο διαφορετικά είμαστε στο πρώτο ενδεχόμενο. Όμοια ελέγχονται και οι άλλες περιπτώσεις.
Ας υποθέσουμε λοιπόν δίχως βλάβη της γενικότητας οτι (οι υπολοιπες περιπτώσεις λειτουργούν αντίστοιχα με αυτήν).
Ας γράψουμε τον πίνακα όπου . Τότε η εξής ακολουθία επαναλαμβάνεται φορές:
(i) Ο Αντρέας επιλέγει τα κελιά
(ii) Ο Βασιλης αφαιρεί απο όλα (διαφορετικά )
(iii) Ο Αντρέας επιλέγει το άκρο (που τώρα ισούται με )
(iv) Ο Βασιλης προσθέτει (διαφορετικά ).
Συνεπώς μετά απο επαναλήψεις ο πίνακας έχει την μορφή
Στην συνέχεια ο Αντρέας επαναλαμβάνει με τα κελιά , μετά με κ.ο.κ μέχρι . Έτσι στο τέλος και συνεπώς δημιουργήσαμε το δεύτερο ενδεχόμενο.
Για κάθε πίνακα μήκους ο Αντρέας μπορεί να διαλέξει κινήσεις ώστε να δημιουργήσει σίγουρα ένα απο τα παρακάτω ενδεχόμενα:
(i) Ενδεχόμενο πρώτο: Τουλάχιστον ένα απο τα δύο άκρα του πίνακα είναι πολλαπλάσιο του .
(ii) Ενδεχόμενο δεύτερο: Όλα τα στοιχεία εκτός των δύο άκρων του πίνακα είναι πολλαπλάσια του .
Βλέπουμε εύκολα οτι τότε συνεπάγεται οτι για κάθε πίνακα μήκους , είναι πάντα εφικτό για τον Αντρέα να κάνει όλα πλην απο τα κελιά του πολλαπλάσια του . Ο λόγος είναι ο εξής. Εάν ο Αντρέας δημιουργήσει το δεύτερο ενδεχόμενο τότε όλα τα στοιχεία εκτός ίσως τα δύο άκρα του πίνακα είναι πολλαπλάσια του . Αντιθέτως, εάν πραγματοποιήσει το πρώτο ενδεχόμενο τότε μπορεί να προχωρήσει επαγωγικά στον πίνακα που αποτελείται απο όλα τα κελιά του αρχικού πλην του άκρου που έχει γίνει πολλαπλάσιο του .
Για να αποτρέψει ο Βασίλης το πρώτο ενδεχόμενο, πρέπει να αποτρέψει την περίπτωση οπου το ένα άκρο του πίνακα ισούται με και το δεύτερο με . Διαφορετικά ο Αντρέας μπορεί να διαλέξει τα κελιά (θα χρησιμοποιήσω αυτόν τον συμβολισμό για να συμβολίσω οτι ο Αντρέας επέλεξε τα κελιά ανάμεσα και συμπεριλαμβανομένων του πρώτου και του n-οστού.) Τότε είτε ο Βασίλης προσθέσει είτε αφαιρέσει θα θέσει ένα κελί στο άκρο ως πολλαπλάσιο του και συνεπώς θα δημιουργήσει το πρώτο ενδεχόμενο που θέλει να αποτρέψει.
Θα δείξουμε οτι εάν ο Βασίλης προσπαθήσει να αποτρέψει το πρώτο ενδεχόμενο τότε ο Αντρέας μπορεί να τον υποχρεώσει να δημιουργήσει το δεύτερο ενδεχόμενο. Έστω οι τιμές στα δύο άκρα. Τότε και διαφορετικά θα είμαστε στο πρώτο ενδεχόμενο.
Λήμμα: Μπορούμε να κάνουμε κινήσεις ώστε ακριβώς ένα απο τα δύο άκρα να ισούται με χωρίς να αλλάξουμε τα ενδιάμεσα κελιά.
Απόδειξη: Εάν τότε ο Αντρέας διαλέγει το κελί και ο Βασίλης πρέπει να προσθέσει στο διαφορετικά είμαστε στο πρώτο ενδεχόμενο. Όμοια ελέγχονται και οι άλλες περιπτώσεις.
Ας υποθέσουμε λοιπόν δίχως βλάβη της γενικότητας οτι (οι υπολοιπες περιπτώσεις λειτουργούν αντίστοιχα με αυτήν).
Ας γράψουμε τον πίνακα όπου . Τότε η εξής ακολουθία επαναλαμβάνεται φορές:
(i) Ο Αντρέας επιλέγει τα κελιά
(ii) Ο Βασιλης αφαιρεί απο όλα (διαφορετικά )
(iii) Ο Αντρέας επιλέγει το άκρο (που τώρα ισούται με )
(iv) Ο Βασιλης προσθέτει (διαφορετικά ).
Συνεπώς μετά απο επαναλήψεις ο πίνακας έχει την μορφή
Στην συνέχεια ο Αντρέας επαναλαμβάνει με τα κελιά , μετά με κ.ο.κ μέχρι . Έτσι στο τέλος και συνεπώς δημιουργήσαμε το δεύτερο ενδεχόμενο.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Πάλι αριθμοί στον πίνακα
Πολύ ωραία. Η δική μου λύση είναι λίγο διαφορετική:
Λήμμα 1: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να κάνω όλους τους υπόλοιπους ίσους .
Λήμμα 2: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να κάνω όλους τους υπόλοιπους πολλαπλάσια του .
Ασφαλώς αν δείξω το Λήμμα 2, τότε ο Αντρέας κερδίζει. (Είτε επαγωγικά όπως στην απόδειξη του Ταρατόρη αν συμβεί η πρώτη περίπτωση, είτε άμεσα αν συμβεί η δεύτερη.)
Για να δείξω ότι μπορώ να πάω από το Λήμμα 1 στο Λήμμα 2 αρκεί να δείξω ότι αν έχω τρεις αριθμούς τότε μπορώ να κάνω έναν από αυτούς πολλαπλάσιο του . [Σκεφτόμαστε ότι ο αντιστοιχεί στον , ο στους και ο στον .]
Αυτό είναι σχετικά εύκολο. Αρχικά κάνω τους περιττούς και τον άρτιο. Μπορώ να υποθέσω ότι αφού αλλιώς τελείωσα. Αν τότε ο ένας είναι ισότιμος με και ο άλλος με . Αν τώρα ο Αντρέας επιλέξει τους τότε ένας από αυτούς σίγουρα θα γίνει πολλαπλάσιο του . Μπορούμε λοιπόν να υποθέσουμε ότι και οι δύο είναι ισότιμοι με . (Η άλλη περίπτωση είναι παρόμοια.) Επιλέγοντας τους για να μην γίνει ο πολλαπλάσιο του αναγκαστικά ο Βασίλης θα προσθέσει και στους δύο αριθμούς. Τότε όμως έχουμε και οπότε αν ο Αντρέας επιλέξει τους ένας από τους θα γίνει πολλαπλάσιο του .
Μένει να αποδείξουμε το Λήμμα 1. Θα δείξουμε επαγωγικά το εξής.
Λήμμα 3: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά) και έστω ότι για κάποιο . Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να πετύχω .
Απόδειξη: Ξεκινάω κάνοντας τους και περιττούς. Μπορώ να υποθέσω πως είναι και οι δύο ισότιμοι αλλιώς μπορώ να κάνω τον ένα πολλαπλάσιο του όπως προηγουμένως. Χωρίς βλάβη της γενικότητας έχω . Τώρα επιλέγω αν χρειαστεί τον ώστε να έχει διαφορετική αρτιότητα από τους . Άρα οι αριθμοί θα είναι μιας από τις δύο πιο κάτω μορφές
(α)
ή
(β)
Στην περίπτωση (α) επιλέγω τους και είτε ο θα γίνει πολλαπλάσιο του είτε θα έχω .
Στην περίπτωση (β) πάλι καταλήγω σε επιθυμητό αποτέλεσμα αν επιλέξω τους .
Ίσως λίγο δύσκολο για τον Αρχιμήδη που το έβαλα αλλά αρκετά πιο εύκολο από την συνέχεια που βρίσκεται εδώ.
Λήμμα 1: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να κάνω όλους τους υπόλοιπους ίσους .
Λήμμα 2: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά). Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να κάνω όλους τους υπόλοιπους πολλαπλάσια του .
Ασφαλώς αν δείξω το Λήμμα 2, τότε ο Αντρέας κερδίζει. (Είτε επαγωγικά όπως στην απόδειξη του Ταρατόρη αν συμβεί η πρώτη περίπτωση, είτε άμεσα αν συμβεί η δεύτερη.)
Για να δείξω ότι μπορώ να πάω από το Λήμμα 1 στο Λήμμα 2 αρκεί να δείξω ότι αν έχω τρεις αριθμούς τότε μπορώ να κάνω έναν από αυτούς πολλαπλάσιο του . [Σκεφτόμαστε ότι ο αντιστοιχεί στον , ο στους και ο στον .]
Αυτό είναι σχετικά εύκολο. Αρχικά κάνω τους περιττούς και τον άρτιο. Μπορώ να υποθέσω ότι αφού αλλιώς τελείωσα. Αν τότε ο ένας είναι ισότιμος με και ο άλλος με . Αν τώρα ο Αντρέας επιλέξει τους τότε ένας από αυτούς σίγουρα θα γίνει πολλαπλάσιο του . Μπορούμε λοιπόν να υποθέσουμε ότι και οι δύο είναι ισότιμοι με . (Η άλλη περίπτωση είναι παρόμοια.) Επιλέγοντας τους για να μην γίνει ο πολλαπλάσιο του αναγκαστικά ο Βασίλης θα προσθέσει και στους δύο αριθμούς. Τότε όμως έχουμε και οπότε αν ο Αντρέας επιλέξει τους ένας από τους θα γίνει πολλαπλάσιο του .
Μένει να αποδείξουμε το Λήμμα 1. Θα δείξουμε επαγωγικά το εξής.
Λήμμα 3: Έστω οι αριθμοί που είναι γραμμένοι στον πίνακα (με αυτήν την σειρά) και έστω ότι για κάποιο . Τότε είτε μπορώ να κάνω ένα από τους πολλαπλάσιο του είτε μπορώ να πετύχω .
Απόδειξη: Ξεκινάω κάνοντας τους και περιττούς. Μπορώ να υποθέσω πως είναι και οι δύο ισότιμοι αλλιώς μπορώ να κάνω τον ένα πολλαπλάσιο του όπως προηγουμένως. Χωρίς βλάβη της γενικότητας έχω . Τώρα επιλέγω αν χρειαστεί τον ώστε να έχει διαφορετική αρτιότητα από τους . Άρα οι αριθμοί θα είναι μιας από τις δύο πιο κάτω μορφές
(α)
ή
(β)
Στην περίπτωση (α) επιλέγω τους και είτε ο θα γίνει πολλαπλάσιο του είτε θα έχω .
Στην περίπτωση (β) πάλι καταλήγω σε επιθυμητό αποτέλεσμα αν επιλέξω τους .
Ίσως λίγο δύσκολο για τον Αρχιμήδη που το έβαλα αλλά αρκετά πιο εύκολο από την συνέχεια που βρίσκεται εδώ.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 12 επισκέπτες