EMC PROBLEM 2

Συντονιστές: cretanman, ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ, socrates

simantiris j.
Δημοσιεύσεις: 245
Εγγραφή: Σάβ Ιαν 18, 2014 5:07 pm

EMC PROBLEM 2

#1

Μη αναγνωσμένη δημοσίευση από simantiris j. »

Για δυο θετικούς ακέραιους a και b η Ίβιτσα και η Μαρίκα παίζουν το ακόλουθο παιχνίδι:Δοθέντων δυο σωρών με a και b μπισκότα,σε κάθε σειρά ένας παίκτης παίρνει 2n μπισκότα από ένα σωρό,από τα οποία τρώει τα n και τα υπόλοιπα n τα τοποθετεί στον άλλο σωρο,με τον n να είναι τυχαίος σε κάθε κίνηση.Ο παίκτης που δε μπορεί να κάνει κίνηση χάνει.Οι παίκτες παίζουν εναλλάξ με την Ίβιτσα να παίζει πρώτη.Υποθέτοντας ότι οι δυο παίκτριες παίζουν βέλτιστα,να βρεθούν τα ζεύγη (a,b) για τα οποία η Μαριίκα έχει στρατηγική νίκης.
Σημαντήρης Γιάννης

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

Re: EMC PROBLEM 2

#2

Μη αναγνωσμένη δημοσίευση από Demetres »

Θα δείξουμε ότι αν |a-b| \in \{0,1\} τότε κερδίζει αυτή που παίζει δεύτερη αλλιώς κερδίζει αυτή που παίζει πρώτη. Αυτό θα το δείξουμε ακόμη και αν a=0 ή b=0. [Οπότε η Μαρίκα κερδίζει αν και μόνο αν |a-b| \leqslant 1.]

Θα το δείξουμε με ισχυρή επαγωγή στο a+b.

Αν a+b=0 τότε a=b=0 και ασφαλώς κερδίζει αυτή που παίζει δεύτερη αφού η πρώτη δεν μπορεί να παίξει.

Ας υποθέσουμε λοιπόν ότι a+b > 0. Έστω αρχικά ότι |a-b| \in \{0,1\}. Όπως και να παίξει αυτή που παίζει πρώτη, ο ένας αριθμός θα μειωθεί τουλάχιστον κατά 2 και ο άλλος θα αυξηθεί τουλάχιστον κατά 1. Άρα η διαφορά σε απόλυτη τιμή θα γίνει τουλάχιστον 2. Οπότε από την επαγωγική υπόθεση, αφού το a+b μειώθηκε, μετά την κίνηση της πρώτης παίκτριας, αυτή που θα παίζει πρώτη στην επόμενη κατάσταση, δηλαδή αυτή που έπαιζε δεύτερη αρχικά, θα κερδίζει. Άρα όντως αν |a-b| \in \{0,1\} τότε κερδίζει αυτή που παίζει δεύτερη.

Έστω τώρα ότι |a-b| \geqslant 2. Χωρίς βλάβη της γενικότητας a < b. Τότε μπορούμε να γράψουμε b = a+3k-1 ή b = a+3k ή b = a+3k+1 για κάποιο k \geqslant 1. Σε όλες τις περιπτώσεις αυτή που παίζει πρώτη παίρνει 2k μπισκότα από τον σωρό με τα b μπισκότα, τρώει τα k και τοποθετεί τα υπόλοιπα k στην άλλη σωρό. Τώρα έχουν μείνει λιγότερα μπισκότα, αυτή που έπαιζε πρώτη παίζει δεύτερη, και μένει μια κατάσταση όπου στην μία σωρό έχουμε a+k και στην άλλη a+k-1 ή a+k ή a+k+1. Η διαφορά είναι το πολύ 1 και άρα από την επαγωγική υπόθεση αυτή που έπαιζε αρχικά πρώτη και τώρα δεύτερη κερδίζει.
Απάντηση

Επιστροφή στο “Θέματα διαγωνισμών (ΕΜΕ, ΚΥΜΕ, BMO, JBMO, IMO, Kangaroo κλπ)”

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

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