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

Σε ένα ορθογώνιο κομμάτι σοκολάτας που αποτελείται από 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 και βρείτε ποια πρέπει να είναι η πρώτη κίνηση του πρώτου παίκτη.

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

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 γραμμές αναπτύξτε την άποψή σας για το ποιο από τα δυο παιχνίδια είναι πιο δύσκολο.