Προβλήματα Μαθηματικών

Απρίλιος 5, 2012

Νικητήρια στρατηγική

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 2:30 μμ

Το πρόβλημα προτείνει ο Αλέξανδρος Γαλανάκης,

Θεωρούμε ένα παιχνίδι που παίζεται απο δύο παίχτες. Το παιχνίδι παίζεται ως εξής. Υπάρχει μια στίβα απο n μάρκες στο τραπέζι και ο παίχτης που παίζει αφαιρεί από τη στίβα από 1 μέχρι k μάρκες κάθε φορά, με k < n. Οι παίχτες παίζουν εναλλάξ. Νικητής είναι αυτός που αφαιρεί απο τη στίβα τις τελευταίες μάρκες. Το ερώτημα είναι ποιος από τους δυο παίχτες μπορεί να έχει στρατηγική νίκης και ποιά είναι αυτή.

Advertisements

2 Σχόλια »

  1. Έστω ότι n=r(k+1)+s,\;\; r\in \mathbb{N} με s\in\{0,1,\ldots,k\}.
    Η απάντηση είναι ότι αν s=0 ο παίχτης που παίζει δεύτερος έχει στρατηγική λύσης ενώ αν s\neq0 έχει στρατηγική λύσης ο παίχτης που παίζει πρώτος . (\star)

    Η στρατηγική λύσης πάει ως εξής:
    Αν σε κάποιο βήμα ο παίχτης X αφήσει στη στοίβα m(k+1) μάρκες τότε όσες μάρκες και να αφαιρέση ο παίχτης Y τότε την επόμενη φορά που θα παίξει ο παίχτης X θα μπορέσει να αφήσει στη στοίβα (m-1)(k+1)=m(k+1)-(k+1) μάρκες. Συνεχίζοντας με αυτό το τρόπο σε κάποια στιγμή ο παίχτης X θα αφήσει στη στοίβα k+1 μάρκες και στο επόμενο βήμα θα κερδίσει.

    Οπότε συνεχίζοντας στο (\star) αν s=0 ο παίχτης που παίζει δεύτερος, για να κερδίσει, αφήνει στη στοίβα (r-1)(k+1) μάρκες ενώ αν s\neq0 ο παίχτης που παίζει πρώτος αφήνει στη στοίβα r(k+1) μάρκες και μπορεί να κερδίσει.

    Μου αρέσει!

    Σχόλιο από Pambos — Απρίλιος 5, 2012 @ 7:28 μμ

  2. Ακριβώς αυτό ειναι… πολυ σωστα!!!

    Μου αρέσει!

    Σχόλιο από alexandrosgalanakis — Απρίλιος 5, 2012 @ 8:50 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: