Στρατηγική Νίκης

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

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

Στρατηγική Νίκης

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Δευ Ιούλ 31, 2017 2:03 pm

Ο Γιάννης και ο Βασίλης παίζουν το εξής παιχνίδι: Ο Βασίλης γράφει στον πίνακα ένα σύνολο A από 2018 διαφορετικούς μεταξύ τους θετικούς ακεραίους και στην συνέχεια ένα σύνολο B από 2017 διαφορετικούς μεταξύ τους θετικούς ακεραίους που όμως δεν περιέχει το S_A(άθροισμα στοιχείων του A). Σε κάθε γύρo ο Γιάννης αθροίζει ένα από τα στοιχεία του A με το άθροισμα που προέκυψε από τον προηγούμενο (Κάθε στοιχείο μπορεί να αθροιστεί μόνο μία φορά). Αν το άθροισμα που προκύπτει από το τέλος κάποιου γύρου ανήκει στο B τότε κερδίζει ο Βασίλης, διαφορετικά κερδίζει ο Γιάννης. Ποιος έχει στρατηγική νίκης;


Bye :')

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

Re: Στρατηγική Νίκης

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιούλ 31, 2017 11:54 pm

Κερδίζει ο Γιάννης.

Θα το αποδείξουμε με επαγωγή στο n όπου υποθέτουμε ότι το σύνολο A έχει n+1 στοιχεία και το σύνολο B έχει n στοιχεία.

Για n=0 είναι προφανές. Έστω τώρα ότι ισχύει για n=k και έστω ένα σύνολο A = \{a_1,\ldots,a_{k+2}\} με k+2 στοιχεία και ένα σύνολο B=\{b_1,\ldots,b_{k+1}\} με k+1 στοιχεία. Έστω επίσης ότι το B δεν περιέχει το στοιχείο S_A = a_1 + \cdots + a_{k+2}.

Κοιτάμε τα k+2 στοιχεία S_A - a_1,S_A-a_2,\ldots,S_A - a_{k+2}. Είναι όλα διαφορετικά μεταξύ τους οπότε υπάρχει τουλάχιστον ένα το οποίο δεν ανήκει στο B, έστω το S_A-a_i.

Θέτω A' = A \setminus \{a_i\} και B' = B \setminus \{b_{k+1}\}. Από τα πιο πάνω το B' δεν περιέχει το S_{A'} οπότε από την επαγωγική υπόθεση ο Γιάννης κερδίζει το παιγνίδι με τα σύνολα A',B'. Τότε όμως κερδίζει το παιγνίδι και με τα σύνολα A,B ακολουθώντας πρώτα την στρατηγική του παιγνιδιού με τα σύνολα A',B' και επιλέγοντας το a_i στο τέλος.


jason.prod
Δημοσιεύσεις: 135
Εγγραφή: Τρί Φεβ 25, 2014 5:29 pm

Re: Στρατηγική Νίκης

#3

Μη αναγνωσμένη δημοσίευση από jason.prod » Κυρ Αύγ 06, 2017 12:42 pm

Να σημειωθεί ότι το πρόβλημα μάλλον δεν είναι για επίπεδο Αρχιμήδη, αφού αποτελεί, στην ουσία, το πρόβλημα C7 της IMO Shortlist 2009 και ταυτόχρονα το πρόβλημα 6 της ίδιας ολυμπιάδας!


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

Re: Στρατηγική Νίκης

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Αύγ 12, 2017 12:07 am

jasonmaths4ever έγραψε:Να σημειωθεί ότι το πρόβλημα μάλλον δεν είναι για επίπεδο Αρχιμήδη, αφού αποτελεί, στην ουσία, το πρόβλημα C7 της IMO Shortlist 2009 και ταυτόχρονα το πρόβλημα 6 της ίδιας ολυμπιάδας!
Μετακινήθηκε στο Προχωρημένο Επίπεδο. Μόλις κοίταξα στα επίσημα στατιστικά και βλέπω ότι μόλις 3 άτομα το έλυσαν! Με παραξένεψε μιας και δεν το βρήκα τόσο δύσκολο. Π.χ. το φετινό (δηλαδή του 2017) πρόβλημα 5 το βρήκα πολύ δυσκολότερο! Μάλλον παίζει μεγάλο ρόλο και η ψυχολογία.


Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1302
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Στρατηγική Νίκης

#5

Μη αναγνωσμένη δημοσίευση από silouan » Σάβ Αύγ 12, 2017 12:28 am

Δείτε και εδώ: 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." :D

Εδώ μαζεμένες οι αποδείξεις που εμφανίστηκαν στο polymath
http://michaelnielsen.org/polymath1/ind ... mo_2009_q6


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

Re: Στρατηγική Νίκης

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Αύγ 13, 2017 2:06 pm

silouan έγραψε:Δείτε και εδώ: https://artofproblemsolving.com/communi ... 51p1562840
Δημήτρη, με μια ματιά δεν είδα τη λύση σου να εμφανίζεται μεταξύ αυτών. Για να είμαι ειλικρινής ψάχνω να βρω αν υπάρχει κάποιο κενό.
Είναι ουσιαστικά η ίδια με αυτήν εδώ. Εν τέλει όμως υπάρχει πρόβλημα με την λύση. (Αν και δεν είδα να αναφέρεται εκεί.)

Το πρόβλημα είναι ότι μπορεί κάποιο από τα αθροίσματα στο παιγνίδι με τα σύνολα A',B' να ισούται με το b_{k+1}.

Θα πρέπει να το σκεφτώ ξανά. Εκ πρώτης όψεως δεν φαίνεται να φτιάχνεται εύκολα.


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

Re: Στρατηγική Νίκης

#7

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 14, 2017 12:24 pm

Τελικά παραδέχομαι ότι ήταν δύσκολο. :) Η πρώτη μου απόδειξη ήταν ουσιαστικά εντελώς λανθασμένη. :( Μου πήρε αρκετό χρόνο να βρω σωστή ελπίζω λύση. Μάλιστα, επειδή είχα ρίξει μια ματιά στις λύσεις στο AOPS για να δω αν υπάρχει παρόμοια λύση με την δική μου, ήξερα πως η λύση είναι επαγωγική. Αλλιώς ίσως τα παρατούσα μιας και δοκίμασα πολλούς τρόπους μέχρι να φτάσω στην λύση.

Έστω λοιπόν a_1 < \cdots < a_{n+1} τα στοιχεία του A και b_1 < \cdots < b_{n} τα στοιχεία του B. Έστω επίσης ότι το ζητούμενο ισχύει για κάθε k< n.

Περίπτωση 1: S_A - a_{n+1} \notin B

Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι A' = A \setminus \{a_{n+1}\} και B' = B \setminus \{b_n\}. Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Μετά επιλέγουμε το a_n και κερδίζουμε το αρχικό παιγνίδι.

Περίπτωση 2: S_A - a_{n+1} = b_n

Εφαρμόζουμε την επαγωγική υπόθεση στο παιγνίδι A' = A \setminus \{a_{n+1}\} και B' = B \setminus \{b_n\}. Επαγωγικά κερδίζουμε αυτό το παιγνίδι. Έστω ότι στο τελευταίο βήμα επιλέξαμε το a_i. Πριν να επιλέξουμε το a_i είμαστε εντάξει και στο αρχικό παιγνίδι. Όταν επιλέξουμε το a_i έχουμε πρόβλημα αφού θα φτάσουμε στο b_n. Επιλέγουμε όμως πρώτα το a_{n+1} και μετά το a_i και είμαστε εντάξει. Πράγματι επειδή a_{n+1} > a_i, όταν επιλέξουμε το a_{n+1} θα πάμε πιο πέρα από το b_n.

Περίπτωση 3: S_A - a_{n+1} = b_r με r<n.

Κοιτάζουμε τα 2n+1 στοιχεία

\displaystyle{S_A - a_1 > S_A - a_2 > \cdots > S_A - a_n > S_A - a_{n+1} > S_A - a_1 - a_{n+1} > \cdots > S_A - a_n - a_{n+1}}

Θα υπάρχουν τουλάχιστον n+1 που δεν ανήκουν στο B. Σε αυτά δεν συμπεριλαμβάνεται το S_A - a_{n+1} = b_r. Άρα θα υπάρχει i με S_A - a_i, S_A - a_i - a_{n+1} \notin B.

Παίζουμε το παιγνίδι με A'' = A \setminus\{a_i,a_{n+1}\} και B'' = \{b_1,\ldots,b_{r-1\}. Επαγωγικά μπορούμε να κερδίσουμε το παιγνίδι αφού S_{A''} \notin B'' και |A''| = n-1 > r-1 = |B''|.

Τότε όμως κερδίζουμε και το αρχικό παιγνίδι. Πράγματι, στο επόμενο βήμα επιλέγουμε το a_n και έχουμε άθροισμα S_A - a_i \notin B. Έπειτα επιλέγουμε το a_i και τελειώσαμε.


Απάντηση

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

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

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