Πρόσθεση διαιρετών μέχρι το 2026

[∫ot.T.]

Είδα αυτό το πρόβλημα σήμερα, το έλυσα αλλά νιώθω πως έχω κάνει κάποιο λάθος.

Δύο παίκτες παίζουν εναλλάξ ένα παιχνίδι σε έναν πίνακα που αρχικά έχει γραμμένο τον αριθμό 2. Σε κάθε κίνηση ο παίκτης που παίζει σβήνει τον εκάστοτε αριθμό από τον πίνακα και τον αντικαθιστά με τον , όπου ένας διαιρέτης του . Όποιος παίκτης υπερβεί τον αριθμό 2026 χάνει. Να προσδιορίσεται αν και ποιος παίκτης έχει στρατηγική νίκης.

[αρψ2400]

Είδα αυτό το πρόβλημα σήμερα, το έλυσα αλλά νιώθω πως έχω κάνει κάποιο λάθος.

Δύο παίκτες παίζουν εναλλάξ ένα παιχνίδι σε έναν πίνακα που αρχικά έχει γραμμένο τον αριθμό 2. Σε κάθε κίνηση ο παίκτης που παίζει σβήνει τον εκάστοτε αριθμό από τον πίνακα και τον αντικαθιστά με τον , όπου ένας διαιρέτης του . Όποιος παίκτης υπερβεί τον αριθμό 2026 χάνει. Να προσδιορίσεται αν και ποιος παίκτης έχει στρατηγική νίκης.

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

[∫ot.T.]

Εγώ το πήγα ανάποδα.

Αρχικά είναι προφανές πως είτε αρχίσουμε από το είτε από το είναι το ίδιο. Άρα έστω ότι αρχίζουμε από το .

Αν ο δεύτερος είχε στρατηγική νίκης στο τότε, εφόσον παίζει ο πρώτος, είτε πάει στο είτε πάει στο τελικά θα κερδίσει ο δεύτερος. Άρα ξεκινόντας από τα ή θα κερδίζει ο πρώτος (αφού ξεκινόντας από το νικά ο δεύτερος που μετά θα είναι ο πρώτος που θα παίζει).

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

[αρψ2400]

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

[αρψ2400]

Μία παραλλαγή του αρχικού προβλήματος:
Δύο παίκτες παίζουν εναλλάξ ένα παιχνίδι σε έναν πίνακα που αρχικά έχει γραμμένο τον αριθμό . Σε κάθε κίνηση ο παίκτης που παίζει σβήνει τον εκάστοτε αριθμό από τον πίνακα και τον αντικαθιστά με τον , όπου ένας διαιρέτης του (ο μπορεί να είναι και ο ). Όποιος παίκτης υπερβεί τον αριθμό χάνει. Να προσδιορίσετε αν κάποιος παίκτης έχει ,και ποια , στρατηγική νίκης .