Σελίδα 1 από 1

Συνδυαστική από Ρουμανία

Δημοσιεύτηκε: Δευ Φεβ 27, 2017 12:07 pm
από harrisp
Δυο παίκτες, οι A και B, παίρνουν εναλλάξ πέτρες από μία στοίβα με n>1πέτρες. Παίζει πρώτος ο A και στην πρώτη του κίνηση επιτρέπεται να πάρει από μία μέχρι n − 1 πέτρες. Ακολούθως κάθε παίκτης επιτρέπεται να πάρει από μία μέχρι k πέτρες όπου k ο αριθμός των πετρών που πήρε ο άλλος παίκτης στην τελευταία του κίνηση. Ο παίκτης που παίρνει την τελευταία πέτρα κερδίζει. Ποιος παίκτης έχει στρατηγική νίκης;

Re: Συνδυαστική από Ρουμανία

Δημοσιεύτηκε: Δευ Φεβ 27, 2017 1:16 pm
από dement
Αν ο n δεν είναι δύναμη 2 του ο Α έχει στρατηγική νίκης. Αρκεί να παίρνει κάθε φορά τη μεγαλύτερη δύναμη του 2 που διαιρεί τον αριθμό των πετρών. Κάνοντας αυτό, αυξάνει τον εκθέτη του 2 στην παραγοντοποίηση του αριθμού των πετρών ενώ ο B δεν μπορεί παρά να τον επαναφέρει ή να τον μειώσει ακόμα περισσότερο. Έτσι, ο Α συνεχίζει τη στρατηγική του μέχρι να του μείνουν 2^k πέτρες που παίρνει με τη μία.

Αν ο n είναι δύναμη του 2 τα πράγματα αντιστρέφονται. Αφού ο A δεν μπορεί να πάρει όλες τις πέτρες, μοιραία θα μειώσει τον εκθέτη του 2 στην παραγοντοποίηση του αριθμού των πετρών και τώρα ο Β ακολουθεί τη θανατηφόρα στρατηγική.

Re: Συνδυαστική από Ρουμανία

Δημοσιεύτηκε: Δευ Φεβ 27, 2017 1:31 pm
από harrisp
dement έγραψε:Αν ο n δεν είναι δύναμη 2 του ο Α έχει στρατηγική νίκης. Αρκεί να παίρνει κάθε φορά τη μεγαλύτερη δύναμη του 2 που μπορεί. Κάνοντας αυτό, αυξάνει τον εκθέτη του 2 στην παραγοντοποίηση του αριθμού των πετρών ενώ ο B δεν μπορεί παρά να τον επαναφέρει ή να τον μειώσει ακόμα περισσότερο. Έτσι, ο Α συνεχίζει τη στρατηγική του μέχρι να του μείνουν 2^k πέτρες που παίρνει με τη μία.

Αν ο n είναι δύναμη του 2 τα πράγματα αντιστρέφονται. Αφού ο A δεν μπορεί να πάρει όλες τις πέτρες, μοιραία θα μειώσει τον εκθέτη του 2 στην παραγοντοποίηση του αριθμού των πετρών και τώρα ο Β ακολουθεί τη θανατηφόρα στρατηγική.

Σατανικό! :evil: