Σελίδα 1 από 1

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

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

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

Δημοσιεύτηκε: Δευ Ιούλ 31, 2017 11:54 pm
από Demetres
Κερδίζει ο Γιάννης.

Θα το αποδείξουμε με επαγωγή στο 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 στο τέλος.

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

Δημοσιεύτηκε: Κυρ Αύγ 06, 2017 12:42 pm
από jason.prod
Να σημειωθεί ότι το πρόβλημα μάλλον δεν είναι για επίπεδο Αρχιμήδη, αφού αποτελεί, στην ουσία, το πρόβλημα C7 της IMO Shortlist 2009 και ταυτόχρονα το πρόβλημα 6 της ίδιας ολυμπιάδας!

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

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

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

Δημοσιεύτηκε: Σάβ Αύγ 12, 2017 12:28 am
από silouan
Δείτε και εδώ: 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

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

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

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

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

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

Δημοσιεύτηκε: Δευ Αύγ 14, 2017 12:24 pm
από Demetres
Τελικά παραδέχομαι ότι ήταν δύσκολο. :) Η πρώτη μου απόδειξη ήταν ουσιαστικά εντελώς λανθασμένη. :( Μου πήρε αρκετό χρόνο να βρω σωστή ελπίζω λύση. Μάλιστα, επειδή είχα ρίξει μια ματιά στις λύσεις στο 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 και τελειώσαμε.