Putnam 2006/A2

#1

Ο Ανδρέας και ο Βασίλης παίζουν το πιο κάτω παιγνίδι:

Ξεκινούν με μια στοίβα από

πέτρες. Ξεκινώντας από τον Ανδρέα παίρνουν εναλλάξ πέτρες από την στοίβα. Σε κάθε κίνηση ο κάθε παίκτης μπορεί να πάρει p-1

πέτρες για κάποιο πρώτο

που θα επιλέξει.

Κερδίζει ο παίκτης ο οποίος θα πάρει την τελευταία πέτρα.

Να δειχθεί ότι υπάρχουν άπειρα

για τα οποία ο Βασίλης έχει στρατηγική νίκης.

[Δεν χρησιμοποιεί πανεπιστημιακές γνώσεις γι' αυτό την έβαλα στους Seniors. Θα μπορούσε να μπει ακόμη και σε Juniors.]

Επεξεργασία: Προστέθηκε η συνθήκη για το πότε κερδίζει ένας παίκτης!

JimNt. · #2

Demetres έγραψε:Ο Ανδρέας και ο Βασίλης παίζουν το πιο κάτω παιγνίδι:

Ξεκινούν με μια στοίβα από πέτρες. Ξεκινώντας από τον Ανδρέα παίρνουν εναλλάξ πέτρες από την στοίβα. Σε κάθε κίνηση ο κάθε παίκτης μπορεί να πάρει πέτρες για κάποιο πρώτο που θα επιλέξει.

Να δειχθεί ότι υπάρχουν άπειρα για τα οποία ο Βασίλης έχει στρατηγική νίκης.

[Δεν χρησιμοποιεί πανεπιστημιακές γνώσεις γι' αυτό την έβαλα στους Seniors. Θα μπορούσε να μπει ακόμη και σε Juniors.]

Μπορεί να χάνω κάτι, αλλά πιστεύω πως δεν παρέχονται επαρκή δεδομένα. π.χ Πότε κερδίζει ένας παίχτης;

harrisp · #3

JimNt. έγραψε:
Demetres έγραψε:Ο Ανδρέας και ο Βασίλης παίζουν το πιο κάτω παιγνίδι:

Ξεκινούν με μια στοίβα από πέτρες. Ξεκινώντας από τον Ανδρέα παίρνουν εναλλάξ πέτρες από την στοίβα. Σε κάθε κίνηση ο κάθε παίκτης μπορεί να πάρει πέτρες για κάποιο πρώτο που θα επιλέξει.

Να δειχθεί ότι υπάρχουν άπειρα για τα οποία ο Βασίλης έχει στρατηγική νίκης.

[Δεν χρησιμοποιεί πανεπιστημιακές γνώσεις γι' αυτό την έβαλα στους Seniors. Θα μπορούσε να μπει ακόμη και σε Juniors.]
Μπορεί να χάνω κάτι, αλλά πιστεύω πως δεν παρέχονται επαρκή δεδομένα. π.χ Πότε κερδίζει ένας παίχτης;

Προφανώς αν πάρει την τελευταία πέτρα από την στοίβα.

Διονύσιος Αδαμόπουλος · #4

Μια προσπάθεια:

Καταρχάς, θα αποδείξουμε πως υπάρχουν τουλάχιστον δύο

, όπου νικάει σίγουρα ο Βασίλης. Παρατηρούμε πως οι πρώτες δύο περιπτώσεις είναι n=3

και

.

Παράλληλα, έστω $T=\{t_1, t_2, ... , t_k\}$ το σύνολο των αριθμών των πετρών που χάνει αυτός που έχει σειρά. Προφανώς, αν ο Ανδρέας ακολουθήσει την καλύτερη στρατηγική του θα προσπαθήσει αν είναι δυνατόν να αφαιρέσει κατάλληλο αριθμό πετρών έτσι ώστε ο αριθμός των πετρών που θα απομείνουν να είναι αριθμός που ανήκει στο σύνολο

. Με αυτόν τον τρόπο, θα έχει σειρά ο Βασίλης και έτσι ο Ανδρέας θα νικήσει. Αν ο Ανδρέας δεν τα καταφέρει, τότε νικητής θα είναι ο Βασίλης.

Άρα για να είναι το

"ευνοϊκό" για τον Βασίλη , πρέπει: α) $n-(p-1)\neq t_i\Leftrightarrow n+1-t_i\neq p$ για κάθε t_i

που ανήκει στο

και β) $n\neq p-1$ , όπου

πρώτος. Σε περίπτωση που ισχύει κάτι τέτοιο, τότε το

συμπεριλαμβάνεται στο

. Παρατηρούμε ταυτοχρόνως ότι το σύνολο

ταυτίζεται με το σύνολο των

που νικά ο Βασίλης, άρα αρκεί το

να έχει άπειρους όρους.

Έστω πως το

έχει πεπερασμένους όρους και τουλάχιστον δύο, δηλαδή $T=\{t_1, t_2, ... , t_k\}$ .

Έστω $q=t_1\cdot t_2\cdot...\cdot t_k-1$ . Θα δείξουμε ότι το

θα ανήκει στο

. α) Ισχύει προφανώς ότι q+1-t_i

είναι σύνθετος για κάθε t_i

που ανήκει στο

, άρα $q+1-t_i\neq p$ όπου

πρώτος. β) Αφού το q+1

είναι σύνθετος τότε $q+1\neq p \Leftrightarrow q\neq p-1$ . Άρα το

ανήκει στο

. Όμως

για κάθε

που ανήκει στο

, άρα οδηγούμαστε σε άτοπο.

Συνεπώς το σύνολο

είναι δεν είναι πεπερασμένο.

Edit: μερικές βελτιώσεις...

harrisp · #5

Μετά την λύση του Διονύση θα ήθελα να επισημάνω κάτι. Ας θεωρήσουμε αρχικά μερικούς αριθμούς για τους οποίους ο Βασίλης έχει στρατηγική νίκης:

0,3,8,11,32,35 . . .

. Στο σημείο αυτό παρατηρώ ότι έχουμε

0,0+3

.

Δεν νομίζω ότι το γεγονός ότι εμφανίζονται με ζευγάρια που διαφέρουν κατά

είναι τυχαίο.

Θα μπορούσαμε λοιπόν να το γενικεύσουμε;

Διονύσιος Αδαμόπουλος · #6

Συμφωνώ και εγώ το είχα παρατηρήσει και μάλιστα συνεχίζεται με 56, 59

αλλά αμφιβάλλω αν θέματα που αφορούν πρώτους έχουν κανονικότητα (μακάρι να είχαν )

#7

Ωραία Διονύση!

Ένα διαφορετικό τελείωμα:

Ας υποθέσουμε πως το σύνολο

των αριθμών για τους οποίους ο Βασίλης έχει στρατηγική νίκης είναι πεπερασμένο. Έστω $T = \{t_1,\ldots,t_k\}$ με $t_1 < \cdots < t_k$ . Θέτουμε επίσης t_0 = 0

.

Όπως και στην λύση του Διονύση, για κάθε n > t_k

, υπάρχει $i \in \{0,1,\ldots,k\}$ ώστε ο n+1-t_i

να είναι πρώτος.

Έστω n = (t_k+2)! + t_k+1

. Τότε

ο οποίος δεν είναι πρώτος αφού είναι πολλαπλάσιο του t_k+2-t_i

.

#8

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:Μετά την λύση του Διονύση θα ήθελα να επισημάνω κάτι. Ας θεωρήσουμε αρχικά μερικούς αριθμούς για τους οποίους ο Βασίλης έχει στρατηγική νίκης:

. Στο σημείο αυτό παρατηρώ ότι έχουμε

.

Δεν νομίζω ότι το γεγονός ότι εμφανίζονται με ζευγάρια που διαφέρουν κατά είναι τυχαίο.

Θα μπορούσαμε λοιπόν να το γενικεύσουμε;

Δεν είναι τυχαίο. Ισχυρίζομαι ότι ισχύει το εξής:

Έστω $n_0 < n_1 < n_2 < \cdots$ όλοι οι μη αρνητικοί ακέραιοι για του ςοποίους κερδίζει ο Βασίλης ξεκινώντας από το n_1 = 0

. Τότε $n_{2k+1} = n_{2k} + 3$ για κάθε μη αρνητικό ακέραιο

.

Αφήνω την απόδειξη ως άσκηση με την επιπλέον υπόδειξη ότι ισχύει επίσης πως ο $n_{2k}$ είναι πάντα άρτιος.

Διονύσιος Αδαμόπουλος · #9

Έστω πως μέχρι το $n_{2k+1}$ όλα είναι φυσιολογικά, δηλαδή οι όροι πηγαίνουν εναλλάξ από άρτιο σε περιττό και $n_{2l+1}=n_{2l}+3$ για κάθε $l\leq k$ . Τώρα διακρίνουμε

περιπτώσεις.
1) ο $n_{2(k+1)}$ είναι άρτιος
2) ο $n_{2(k+1)}$ είναι περιττός

1) Προφανώς, ισχύει ότι ο $n_{2(k+1)}+1-n_{2l}$ είναι σύνθετος για κάθε $n_{2l}$ . Θα αποδείξουμε ότι $n_{2(k+1)+1}=n_{2(k+1)}+3$ . Για να ισχύει κάτι τέτοιο πρέπει ο $n_{2(k+1)}+4-n_{i}$ να είναι σύνθετος για κάθε $i\leq 2(k+1)$ . Όμως για i=2l

κάτι τέτοιο είναι τετριμμένο, ενώ για i=2l+1

έχουμε ότι: $n_{2(k+1)}+4-n_{2l+1}=n_{2(k+1)}+4-n_{2l}-3=n_{2(k+1)}+1-n_{2l}$ που όπως αναφέραμε είναι σύνθετος. Άρα $n_{2(k+1)+1}=n_{2(k+1)}+3$ .

2)Προφανώς, ισχύει ότι ο $n_{2(k+1)}+1-n_{2l+1}$ είναι σύνθετος για κάθε $n_{2l+1}$ . Ακόμη, δεν υπάρχει κανένα

έτσι $n_{2k+1}\leq n_i \leq n_{2(k+1)}$ . Άρα προφανώς $n_{2(k+1)}-3\neq n_i$ , δηλαδή υπάρχει κάποιο $n_{j}$ , έτσι ώστε ο $n_{2(k+1)}-2-n_j$ να είναι πρώτος. Όμως για j=2l+1

κάτι τέτοιο είναι σαφώς αδύνατο καθώς ο $n_{2(k+1)}-2-n_{2l+1}$ είναι άρτιος, ενώ για j=2l

έχουμε ότι:
$n_{2(k+1)}-2-n_{2l}=n_{2(k+1)}+1-3-n_{2l}=n_{2(k+1)}+1-n_{2l+1}$ που όπως αναφέραμε είναι σύνθετος. Άρα $n_{2(k+1)}-3=n_i$ , πράγμα άτοπο. Άρα η περίπτωση 2) απορρίπτεται.

Έτσι συνεχίζουμε επαγωγικά και η εικασία του Χάρη αποδείχτηκε! (Ήμουν τελείως λάθος που υπέθεσα αρχικά το αντίθετο)

Putnam 2006/A2

Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

Re: Putnam 2006/A2

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