Putnam 2006/A2

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

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

Putnam 2006/A2

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Νοέμ 05, 2016 10:23 am

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

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

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

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

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

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



Λέξεις Κλειδιά:
Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 588
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Putnam 2006/A2

#2

Μη αναγνωσμένη δημοσίευση από JimNt. » Σάβ Νοέμ 05, 2016 1:06 pm

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

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

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

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


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
harrisp
Δημοσιεύσεις: 541
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Putnam 2006/A2

#3

Μη αναγνωσμένη δημοσίευση από harrisp » Σάβ Νοέμ 05, 2016 1:59 pm

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

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

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

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

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


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 800
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Putnam 2006/A2

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Νοέμ 05, 2016 5:29 pm

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

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

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

Άρα για να είναι το n "ευνοϊκό" για τον Βασίλη , πρέπει: α) n-(p-1)\neq t_i\Leftrightarrow n+1-t_i\neq p για κάθε t_i που ανήκει στο T και β) n\neq p-1, όπου p πρώτος. Σε περίπτωση που ισχύει κάτι τέτοιο, τότε το n συμπεριλαμβάνεται στο T. Παρατηρούμε ταυτοχρόνως ότι το σύνολο T ταυτίζεται με το σύνολο των n που νικά ο Βασίλης, άρα αρκεί το T να έχει άπειρους όρους.

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

Έστω q=t_1\cdot t_2\cdot...\cdot t_k-1. Θα δείξουμε ότι το q θα ανήκει στο T. α) Ισχύει προφανώς ότι q+1-t_i είναι σύνθετος για κάθε t_i που ανήκει στο T, άρα q+1-t_i\neq p όπου p πρώτος. β) Αφού το q+1 είναι σύνθετος τότε q+1\neq p \Leftrightarrow q\neq p-1. Άρα το q ανήκει στο T. Όμως q>t_i για κάθε t_i που ανήκει στο T, άρα οδηγούμαστε σε άτοπο.

Συνεπώς το σύνολο T είναι δεν είναι πεπερασμένο.

Edit: μερικές βελτιώσεις...
τελευταία επεξεργασία από Διονύσιος Αδαμόπουλος σε Σάβ Νοέμ 05, 2016 8:38 pm, έχει επεξεργασθεί 2 φορές συνολικά.


Houston, we have a problem!
harrisp
Δημοσιεύσεις: 541
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Putnam 2006/A2

#5

Μη αναγνωσμένη δημοσίευση από harrisp » Σάβ Νοέμ 05, 2016 6:34 pm

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

0,3,8,11,32,35 . . .. Στο σημείο αυτό παρατηρώ ότι έχουμε

0,0+3

8,8+3

32,32+3.

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

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


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 800
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Putnam 2006/A2

#6

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Νοέμ 05, 2016 6:46 pm

Συμφωνώ και εγώ το είχα παρατηρήσει και μάλιστα συνεχίζεται με 56, 59 αλλά αμφιβάλλω αν θέματα που αφορούν πρώτους έχουν κανονικότητα (μακάρι να είχαν )


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

Re: Putnam 2006/A2

#7

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Νοέμ 05, 2016 10:06 pm

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

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

Ας υποθέσουμε πως το σύνολο T των αριθμών για τους οποίους ο Βασίλης έχει στρατηγική νίκης είναι πεπερασμένο. Έστω 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. Τότε n+1-t_i = (t_k+2)! + (t_k+ 2 - t_i) ο οποίος δεν είναι πρώτος αφού είναι πολλαπλάσιο του t_k+2-t_i.


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

Re: Putnam 2006/A2

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Νοέμ 06, 2016 2:22 pm

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

0,3,8,11,32,35 . . .. Στο σημείο αυτό παρατηρώ ότι έχουμε

0,0+3

8,8+3

32,32+3.

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

Θα μπορούσαμε λοιπόν να το γενικεύσουμε;
Δεν είναι τυχαίο. Ισχυρίζομαι ότι ισχύει το εξής:

Έστω n_0 < n_1 < n_2 < \cdots όλοι οι μη αρνητικοί ακέραιοι για του ςοποίους κερδίζει ο Βασίλης ξεκινώντας από το n_1 = 0. Τότε n_{2k+1} = n_{2k} + 3 για κάθε μη αρνητικό ακέραιο k.

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


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 800
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Putnam 2006/A2

#9

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Κυρ Νοέμ 06, 2016 7:51 pm

Έστω πως μέχρι το n_{2k+1} όλα είναι φυσιολογικά, δηλαδή οι όροι πηγαίνουν εναλλάξ από άρτιο σε περιττό και n_{2l+1}=n_{2l}+3 για κάθε l\leq k. Τώρα διακρίνουμε 2 περιπτώσεις.
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}. Ακόμη, δεν υπάρχει κανένα i έτσι 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) απορρίπτεται.

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


Houston, we have a problem!
Απάντηση

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

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

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