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

27 Μαρτίου, 2008

Μία ορθογώνια σοκολάτα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 11:25 μμ

Έχουμε μια ορθογώνια σοκολάτα που αποτελείται από τετραγωνάκια τοποθετημένα σε m γραμμές και n στήλες. Το τετραγωνάκι όμως της πάνω αριστερά γωνίας (και μόνο αυτό) είναι φτιαγμένο από σαπούνι αντί για σοκολάτα.

Δύο παίκτες παίζουν το ακόλουθο παιχνίδι: Όταν έρθει η σειρά κάποιου παίκτη αυτός κόβει ένα κομμάτι σοκολάτα και το τρώει. Η m\times n σοκολάτα μπορεί να κοπεί είτε οριζόντια είτε κάθετα αλλά πλήρως, δηλ.\ αν η σοκολάτα κοπεί οριζόντια τότε αυτή χωρίζεται σε δύο ορθογώνιες σοκολάτες, μια k\times n και μια (m-k)\times n, και ο παίκτης διαλέγει και τρώει ένα από τα δύο ορθογώνια κομμάτια. Ομοίως, αν η σοκολάτα κοπεί κάθετα τότε χωρίζεται σε δυο κομμάτια, ένα m\times k και ένα m\times (n-k). Χάνει ο παίκτης που αναγκάζεται να φάει το τετραγωνάκι με το σαπούνι.

Θα θέλατε να παίζατε πρώτος ή δεύτερος; Η απάντηση εξαρτάται από τα m και n.

8 Σχόλια »

  1. Αν ήταν m=n δεύτερος.
    Αλλιώς πρώτος.

    Μου αρέσει!

    Σχόλιο από yioryos — 28 Μαρτίου, 2008 @ 6:56 μμ

  2. Γιατί;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 28 Μαρτίου, 2008 @ 6:57 μμ

  3. Αν το m είναι διάφορο του n τότε ο παίχτης που παίζει μπορεί να κανει μια κίνηση έτσι ώστε να γίνουν ίσα. Ενώ αν είναι ίσα όποια κίνηση και να κάνει καταλήγουν σε διαφορετικά m n. Επειδή το παιχνίδι τελειώνει στο 1×1 ο παίχτης που έχει mn έχει στρατηγική νίκης.

    Τι γίνεται όμως όταν το σαπουνένιο τετραγωνάκι δεν είναι πάνω αριστερά αλλά κάπου μέσα στη σοκολάτα. Πότε θα θέλατε να παίζετε πρώτος και πότε δεύτερος;

    Μου αρέσει!

    Σχόλιο από ctzamos — 28 Μαρτίου, 2008 @ 9:09 μμ

  4. Πολύ καλό ερώτημα, αλλά δε μπορώ να το απαντήσω.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 30 Μαρτίου, 2008 @ 11:52 πμ

  5. Το πρόβλημα αυτό είναι ισοδύναμο με το παιχνίδι Nim με 4 στήλες. Αν το ορθογώνιο είναι nxm και το κουτακι βρίσκεται στη θέση (x,y) η ικανή και αναγκαία συνθήκη για να κερδίσει ο πρώτος είναι:

    (x-1) xor (y-1) xor (n-x) xor (m-y) != 0

    Όπου (a xor b) ορίζεται ως

    (aN xor bN)…(a1 xor b1)(a0 xor b0)

    για aN…a1a0 και bN…b1b0 η διαδική αναπαράσταση των αριθμών a και b.

    Π.χ.
    Αν έχουμε n=22, m=18, x=8, y=6
    (x-1) = 7 = 0111
    (y-1) = 5 = 0101
    (n-x) =14= 1110
    (m-y)=12= 1100
    xor = 0000
    Οπότε ο πρώτος παίχτης χάνει.
    Στην ειδική περίπτωση όπου x=n,y=m έχουμε
    (m-1) xor (n-1) != 0 δηλαδή m != n.

    Η πράξη xor υπάρχει και στην αριθμομηχανή των Windows.

    Μου αρέσει!

    Σχόλιο από ctzamos — 30 Μαρτίου, 2008 @ 10:37 μμ

  6. Περισσότερα για το nim
    http://en.wikipedia.org/wiki/Nim

    Μου αρέσει!

    Σχόλιο από ctzamos — 30 Μαρτίου, 2008 @ 10:38 μμ

  7. Εξαιρετικό.

    Δεν ήξερα για το NIM. Θα σε πείραζε να εξηγήσεις με λίγα λόγια την αναγωγή τους ενός προβλήματος στο άλλο για τους αναγνώστες του blog;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 31 Μαρτίου, 2008 @ 6:55 μμ

  8. Θεωρώντας σταθερό το κομμάτι από σαπούνι, οι επιτρεπτές μας κινήσεις είναι να μειώσουμε το δεξί το αριστερό, το πάνω η το κάτω τμήμα. Τα τμήματα είναι ανεξάρτητα οπότε μειώνοντας το ένα δεν επηρεάζονται τα άλλα και σε κάθε γύρω μειωνουμε ακριβώς ένα τμήμα κατα όσες μονάδες θέλουμε. Ο παίχτης που δεν θα έχει τμήμα να μειώσει χάνει το παιχνίδι γιατί μένει με το σαπουνένιο κομμάτι. Αυτό είναι ακριβώς το παιχνίδι nim με 4 στοίβες

    Μου αρέσει!

    Σχόλιο από ctzamos — 1 Απριλίου, 2008 @ 7:29 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.