Στρατηγική Νίκης
Συντονιστές: Demetres, socrates, silouan
Στρατηγική Νίκης
Ο Γιάννης και ο Βασίλης παίζουν το εξής παιχνίδι: Ο Βασίλης γράφει στον πίνακα ένα σύνολο από διαφορετικούς μεταξύ τους θετικούς ακεραίους και στην συνέχεια ένα σύνολο από διαφορετικούς μεταξύ τους θετικούς ακεραίους που όμως δεν περιέχει το (άθροισμα στοιχείων του ). Σε κάθε γύρo ο Γιάννης αθροίζει ένα από τα στοιχεία του με το άθροισμα που προέκυψε από τον προηγούμενο (Κάθε στοιχείο μπορεί να αθροιστεί μόνο μία φορά). Αν το άθροισμα που προκύπτει από το τέλος κάποιου γύρου ανήκει στο τότε κερδίζει ο Βασίλης, διαφορετικά κερδίζει ο Γιάννης. Ποιος έχει στρατηγική νίκης;
Bye :')
Λέξεις Κλειδιά:
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Στρατηγική Νίκης
Κερδίζει ο Γιάννης.
Θα το αποδείξουμε με επαγωγή στο όπου υποθέτουμε ότι το σύνολο έχει στοιχεία και το σύνολο έχει στοιχεία.
Για είναι προφανές. Έστω τώρα ότι ισχύει για και έστω ένα σύνολο με στοιχεία και ένα σύνολο με στοιχεία. Έστω επίσης ότι το δεν περιέχει το στοιχείο .
Κοιτάμε τα στοιχεία . Είναι όλα διαφορετικά μεταξύ τους οπότε υπάρχει τουλάχιστον ένα το οποίο δεν ανήκει στο , έστω το .
Θέτω και . Από τα πιο πάνω το δεν περιέχει το οπότε από την επαγωγική υπόθεση ο Γιάννης κερδίζει το παιγνίδι με τα σύνολα . Τότε όμως κερδίζει το παιγνίδι και με τα σύνολα ακολουθώντας πρώτα την στρατηγική του παιγνιδιού με τα σύνολα και επιλέγοντας το στο τέλος.
Θα το αποδείξουμε με επαγωγή στο όπου υποθέτουμε ότι το σύνολο έχει στοιχεία και το σύνολο έχει στοιχεία.
Για είναι προφανές. Έστω τώρα ότι ισχύει για και έστω ένα σύνολο με στοιχεία και ένα σύνολο με στοιχεία. Έστω επίσης ότι το δεν περιέχει το στοιχείο .
Κοιτάμε τα στοιχεία . Είναι όλα διαφορετικά μεταξύ τους οπότε υπάρχει τουλάχιστον ένα το οποίο δεν ανήκει στο , έστω το .
Θέτω και . Από τα πιο πάνω το δεν περιέχει το οπότε από την επαγωγική υπόθεση ο Γιάννης κερδίζει το παιγνίδι με τα σύνολα . Τότε όμως κερδίζει το παιγνίδι και με τα σύνολα ακολουθώντας πρώτα την στρατηγική του παιγνιδιού με τα σύνολα και επιλέγοντας το στο τέλος.
-
- Δημοσιεύσεις: 141
- Εγγραφή: Τρί Φεβ 25, 2014 5:29 pm
Re: Στρατηγική Νίκης
Να σημειωθεί ότι το πρόβλημα μάλλον δεν είναι για επίπεδο Αρχιμήδη, αφού αποτελεί, στην ουσία, το πρόβλημα C7 της IMO Shortlist 2009 και ταυτόχρονα το πρόβλημα 6 της ίδιας ολυμπιάδας!
Προδρομίδης Κυπριανός-Ιάσων
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Στρατηγική Νίκης
Μετακινήθηκε στο Προχωρημένο Επίπεδο. Μόλις κοίταξα στα επίσημα στατιστικά και βλέπω ότι μόλις 3 άτομα το έλυσαν! Με παραξένεψε μιας και δεν το βρήκα τόσο δύσκολο. Π.χ. το φετινό (δηλαδή του 2017) πρόβλημα το βρήκα πολύ δυσκολότερο! Μάλλον παίζει μεγάλο ρόλο και η ψυχολογία.jasonmaths4ever έγραψε:Να σημειωθεί ότι το πρόβλημα μάλλον δεν είναι για επίπεδο Αρχιμήδη, αφού αποτελεί, στην ουσία, το πρόβλημα C7 της IMO Shortlist 2009 και ταυτόχρονα το πρόβλημα 6 της ίδιας ολυμπιάδας!
Re: Στρατηγική Νίκης
Δείτε και εδώ: https://artofproblemsolving.com/communi ... 51p1562840
Δημήτρη, με μια ματιά δεν είδα τη λύση σου να εμφανίζεται μεταξύ αυτών. Για να είμαι ειλικρινής ψάχνω να βρω αν υπάρχει κάποιο κενό.
Ένα ενδιαφέρον επίσης
https://terrytao.wordpress.com/2009/07/ ... h-project/
Ο Tao γράφει στην αρχή: "I myself worked it out about seven hours after first hearing about the problem, though I was preoccupied with other things for most of that time period."
Εδώ μαζεμένες οι αποδείξεις που εμφανίστηκαν στο polymath
http://michaelnielsen.org/polymath1/ind ... mo_2009_q6
Δημήτρη, με μια ματιά δεν είδα τη λύση σου να εμφανίζεται μεταξύ αυτών. Για να είμαι ειλικρινής ψάχνω να βρω αν υπάρχει κάποιο κενό.
Ένα ενδιαφέρον επίσης
https://terrytao.wordpress.com/2009/07/ ... h-project/
Ο Tao γράφει στην αρχή: "I myself worked it out about seven hours after first hearing about the problem, though I was preoccupied with other things for most of that time period."
Εδώ μαζεμένες οι αποδείξεις που εμφανίστηκαν στο polymath
http://michaelnielsen.org/polymath1/ind ... mo_2009_q6
Σιλουανός Μπραζιτίκος
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Στρατηγική Νίκης
Είναι ουσιαστικά η ίδια με αυτήν εδώ. Εν τέλει όμως υπάρχει πρόβλημα με την λύση. (Αν και δεν είδα να αναφέρεται εκεί.)silouan έγραψε:Δείτε και εδώ: https://artofproblemsolving.com/communi ... 51p1562840
Δημήτρη, με μια ματιά δεν είδα τη λύση σου να εμφανίζεται μεταξύ αυτών. Για να είμαι ειλικρινής ψάχνω να βρω αν υπάρχει κάποιο κενό.
Το πρόβλημα είναι ότι μπορεί κάποιο από τα αθροίσματα στο παιγνίδι με τα σύνολα να ισούται με το .
Θα πρέπει να το σκεφτώ ξανά. Εκ πρώτης όψεως δεν φαίνεται να φτιάχνεται εύκολα.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Στρατηγική Νίκης
Τελικά παραδέχομαι ότι ήταν δύσκολο. Η πρώτη μου απόδειξη ήταν ουσιαστικά εντελώς λανθασμένη. Μου πήρε αρκετό χρόνο να βρω σωστή ελπίζω λύση. Μάλιστα, επειδή είχα ρίξει μια ματιά στις λύσεις στο AOPS για να δω αν υπάρχει παρόμοια λύση με την δική μου, ήξερα πως η λύση είναι επαγωγική. Αλλιώς ίσως τα παρατούσα μιας και δοκίμασα πολλούς τρόπους μέχρι να φτάσω στην λύση.
Έστω λοιπόν τα στοιχεία του και τα στοιχεία του . Έστω επίσης ότι το ζητούμενο ισχύει για κάθε .
Περίπτωση 1:
Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι και . Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Μετά επιλέγουμε το και κερδίζουμε το αρχικό παιγνίδι.
Περίπτωση 2:
Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι και . Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Έστω ότι στο τελευταίο βήμα επιλέξαμε το . Πριν να επιλέξουμε το είμαστε εντάξει και στο αρχικό παιγνίδι. Όταν επιλέξουμε το έχουμε πρόβλημα αφού θα φτάσουμε στο . Επιλέγουμε όμως πρώτα το και μετά το και είμαστε εντάξει. Πράγματι επειδή , όταν επιλέξουμε το θα πάμε πιο πέρα από το .
Περίπτωση 3: με .
Κοιτάζουμε τα στοιχεία
Θα υπάρχουν τουλάχιστον που δεν ανήκουν στο . Σε αυτά δεν συμπεριλαμβάνεται το . Άρα θα υπάρχει με .
Παίζουμε το παιγνίδι με και . Επαγωγικά μπορούμε να κερδίσουμε το παιγνίδι αφού και .
Τότε όμως κερδίζουμε και το αρχικό παιγνίδι. Πράγματι, στο επόμενο βήμα επιλέγουμε το και έχουμε άθροισμα . Έπειτα επιλέγουμε το και τελειώσαμε.
Έστω λοιπόν τα στοιχεία του και τα στοιχεία του . Έστω επίσης ότι το ζητούμενο ισχύει για κάθε .
Περίπτωση 1:
Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι και . Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Μετά επιλέγουμε το και κερδίζουμε το αρχικό παιγνίδι.
Περίπτωση 2:
Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι και . Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Έστω ότι στο τελευταίο βήμα επιλέξαμε το . Πριν να επιλέξουμε το είμαστε εντάξει και στο αρχικό παιγνίδι. Όταν επιλέξουμε το έχουμε πρόβλημα αφού θα φτάσουμε στο . Επιλέγουμε όμως πρώτα το και μετά το και είμαστε εντάξει. Πράγματι επειδή , όταν επιλέξουμε το θα πάμε πιο πέρα από το .
Περίπτωση 3: με .
Κοιτάζουμε τα στοιχεία
Θα υπάρχουν τουλάχιστον που δεν ανήκουν στο . Σε αυτά δεν συμπεριλαμβάνεται το . Άρα θα υπάρχει με .
Παίζουμε το παιγνίδι με και . Επαγωγικά μπορούμε να κερδίσουμε το παιγνίδι αφού και .
Τότε όμως κερδίζουμε και το αρχικό παιγνίδι. Πράγματι, στο επόμενο βήμα επιλέγουμε το και έχουμε άθροισμα . Έπειτα επιλέγουμε το και τελειώσαμε.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες