Μαθηματικά Πληροφορικής

Σε ένα ορθογώνιο κομμάτι σοκολάτας που αποτελείται από m× n τετράγωνα κομμάτια, το κάτω αριστερά τετράγωνο είναι δηλητηριασμένο. Δυο παίκτες παίζουν το εξής παιχνίδι: Εναλλάξ επιλέγουν ένα από τα μικρά τετράγωνα κομμάτια και τρώνε όλα τα κομμάτια που έχουν απομείνει και βρίσκονται δεξιά και πάνω από αυτό, συμπεριλαμβανομένου του επιλεγμένου κομματιού. Για παράδειγμα, στο επόμενο φαίνονται δυο πιθανές κινήσεις, μια για κάθε παίκτη:

o o o o o     o o o         o o
o o o o o --> o o o     --> o o o
o o o o o     o o o o o     o o o o o 
o o o o o     o o o o o     o o o o o

Σκοπός του κάθε παίκτη είναι να αποφύγει να φάει το δηλητηριασμένο τετράγωνο.

1. Δείξτε πως αν η αρχική σοκολάτα έχει περισσότερα από ένα τετράγωνα, τότε ο παίκτης που παίζει πρώτος μπορεί πάντα να κερδίσει. Βοήθεια: Ας υποθέσουμε πως ο πρώτος παίκτης κόβει μόνο το πάνω δεξιά τετράγωνο στην αρχή. Aυτή η κίνηση είτε κερδίζει είτε χάνει. Αν κερδίζει, βρήκαμε μια κίνηση με την οποία κερδίζει ο πρώτος παίκτης. Αν όμως η κίνηση αυτή χάνει, τότε …
2. Αναλύστε το παίγνιο για 3× 3 και βρείτε ποια πρέπει να είναι η πρώτη κίνηση του πρώτου παίκτη.

1. Αυτό το παιχνίδι είναι γνωστό σαν Chomp και εφευρέθηκε από τον David Gale. Μπορείτε να παίξετε το παιχνίδι online.

   Η απόδειξη πως ο πρώτος παίκτης έχει πάντα τρόπο να κερδίσει είναι απλή: Αν κερδίζει με το να κόψει πρώτα το πάνω-δεξιά τετράγωνο έχει καλώς. Αλλιώς, αν αυτή η κίνηση χάνει, τότε ο δεύτερος παίκτης κερδίζει με κάποια πρώτη κίνηση. Το σημαντικό σημείο είναι πως ο πρώτος παίκτης μπορεί να κάνει αυτή την πρώτη κίνηση ο ίδιος και να κερδίσει αυτός.

2. Για 3× 3 σοκολάτα, ο πρώτος παίκτης μπορεί να κερδίσει αν αφαιρέσει στην πρώτη κίνηση ένα τετράγωνο κομμάτι 2× 2. Μετά την πρώτη κίνηση, το παιχνίδι είναι απλό (π.χ. ο πρώτος παίκτης μιμείται την προηγούμενη κίνηση του δεύτερου παίκτη).

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

o o o o o     o o o      
o o o o o --> o o o  --> o o o -->
o o o o o     o o o      o o o     ο ο ο
o o o o o     o o o      o o o     ο ο ο

1. Βρείτε ποιος παίκτης κερδίζει το παιχνίδι για αρχικά μεγέθη σοκολάτας 2× 2 και για 2× 3.
2. Γενικεύστε. Ποιος παίκτης κερδίζει για σοκολάτα αρχικού μεγέθους m× n και με ποια στρατηγική;
3. Συγκρίνετε το παιχνίδι με το προηγούμενο. Σε 3 γραμμές αναπτύξτε την άποψή σας για το ποιο από τα δυο παιχνίδια είναι πιο δύσκολο.

1. Για σοκολάτα 2× 2 κερδίζει ο δεύτερος παίκτης και για 2× 3 ο πρώτος παίκτης, όπως εξηγείται παρακάτω.
2. Ο πρώτος παίκτης κερδίζει αν και μόνο αν η αρχική σοκολάτα δεν είναι τετράγωνη. Αν κάποιος παίκτης μπορεί να αφήσει τετράγωνη σοκολάτα, μπορεί να κερδίσει, γιατί σε κάθε επόμενη κίνηση του μπορεί να αφήνει τετράγωνη σοκολάτα.
3. Το παιχνίδι αυτό είναι σαφώς ποιο εύκολο, αφού γνωρίζουμε ακριβώς πως πρέπει να παίξουμε για να κερδίσουμε. Αντίθετα, το πρώτο παιχνίδι, αν και γνωρίζουμε πως ο πρώτος παίκτης έχει πάντα τρόπο να κερδίσει, δεν έχουμε αποτελεσματικό τρόπο που να περιγράφει τη βέλτιστη στρατηγική. Δείτε και την ιστοσελίδα.