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

JimNt. · #1

Ο Γιάννης και ο Βασίλης παίζουν το εξής παιχνίδι: Ο Βασίλης γράφει στον πίνακα ένα σύνολο

από

διαφορετικούς μεταξύ τους θετικούς ακεραίους και στην συνέχεια ένα σύνολο

από

διαφορετικούς μεταξύ τους θετικούς ακεραίους που όμως δεν περιέχει το S_A

(άθροισμα στοιχείων του

). Σε κάθε γύρo ο Γιάννης αθροίζει ένα από τα στοιχεία του

με το άθροισμα που προέκυψε από τον προηγούμενο (Κάθε στοιχείο μπορεί να αθροιστεί μόνο μία φορά). Αν το άθροισμα που προκύπτει από το τέλος κάποιου γύρου ανήκει στο

τότε κερδίζει ο Βασίλης, διαφορετικά κερδίζει ο Γιάννης. Ποιος έχει στρατηγική νίκης;

#2

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

Θα το αποδείξουμε με επαγωγή στο

όπου υποθέτουμε ότι το σύνολο

έχει

στοιχεία και το σύνολο

έχει

στοιχεία.

Για n=0

είναι προφανές. Έστω τώρα ότι ισχύει για n=k

και έστω ένα σύνολο $A = \{a_1,\ldots,a_{k+2}\}$ με k+2

στοιχεία και ένα σύνολο $B=\{b_1,\ldots,b_{k+1}\}$ με k+1

στοιχεία. Έστω επίσης ότι το

δεν περιέχει το στοιχείο $S_A = a_1 + \cdots + a_{k+2}$ .

Κοιτάμε τα k+2

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

, έστω το

.

Θέτω $A' = A \setminus \{a_i\}$ και $B' = B \setminus \{b_{k+1}\}$ . Από τα πιο πάνω το

δεν περιέχει το $S_{A'}$ οπότε από την επαγωγική υπόθεση ο Γιάννης κερδίζει το παιγνίδι με τα σύνολα A',B'

. Τότε όμως κερδίζει το παιγνίδι και με τα σύνολα A,B

ακολουθώντας πρώτα την στρατηγική του παιγνιδιού με τα σύνολα A',B'

και επιλέγοντας το a_i

στο τέλος.

jason.prod · #3

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

#4

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

Μετακινήθηκε στο Προχωρημένο Επίπεδο. Μόλις κοίταξα στα επίσημα στατιστικά και βλέπω ότι μόλις 3 άτομα το έλυσαν! Με παραξένεψε μιας και δεν το βρήκα τόσο δύσκολο. Π.χ. το φετινό (δηλαδή του 2017) πρόβλημα

το βρήκα πολύ δυσκολότερο! Μάλλον παίζει μεγάλο ρόλο και η ψυχολογία.

#5

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

#6

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

Είναι ουσιαστικά η ίδια με αυτήν εδώ. Εν τέλει όμως υπάρχει πρόβλημα με την λύση. (Αν και δεν είδα να αναφέρεται εκεί.)

Το πρόβλημα είναι ότι μπορεί κάποιο από τα αθροίσματα στο παιγνίδι με τα σύνολα A',B'

να ισούται με το $b_{k+1}$ .

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

#7

Τελικά παραδέχομαι ότι ήταν δύσκολο.

Η πρώτη μου απόδειξη ήταν ουσιαστικά εντελώς λανθασμένη.

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

Έστω λοιπόν $a_1 < \cdots < a_{n+1}$ τα στοιχεία του

και $b_1 < \cdots < b_{n}$ τα στοιχεία του

. Έστω επίσης ότι το ζητούμενο ισχύει για κάθε 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

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

. Σε αυτά δεν συμπεριλαμβάνεται το $S_A - a_{n+1} = b_r$ . Άρα θα υπάρχει

με $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

και τελειώσαμε.

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

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

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

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

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

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

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

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

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