Πρόκειται για το γνωστό πρόβλημα με τις τελείτσες το οποίο (εάν δεν είστε φανατίλες μαθηματικόφιλοι) το ξεχάσατε σίγουρα. (βλέπε αναφορές)

Πρόταση / Λύση

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

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

Ας θεωρήσουμε πίνακα mxn τελειών. Ο πίνακας περιέχει προφανώς αριθμό κουτιών:

Κάθε κουτί έχει εν γένει 4 ακμές, ενώ κάθε ακμή ανήκει σε 2 κουτιά, εκτός αν είναι εξωτερική οπότε ανήκει σε ένα κουτί. Προφανώς ο συνολικός αριθμός των ακμών είναι:

Φαίνεται προφανώς ότι:

Άμεση παρατήρηση 1: Ένας παίκτης μπορεί να κλείσει ταυτόχρονα το πολύ 2 τετράγωνα.

Θεώρημα 1: Στις περιπτώσεις Ι και ΙΙ όπου Αmn=άρτιος ο 2ος παίκτης παίζει τελευταίος και κλείνει τουλάχιστον ένα τετράγωνο.

Πόρισμα 1: Αν m=n=2 είναι Tmn=1 και ο 2ος παίκτης κερδίζει κλείνοντας το μοναδικό τετράγωνο.

Θεώρημα 2: Στην περίπτωση ΙΙΙ όπου Αmn=περιττός ο 1ος παίκτης παίζει τελευταίος και κλείνει τουλάχιστον ένα τετράγωνο.

Θεώρημα 3: Στην περίπτωση Ι όπου Tmn=περιττός το παιχνίδι έχει σίγουρα νικητή.

Μία "κοντόφθαλμη" στρατηγική που μπορεί να εφαρμοσθεί είναι η: "δεν αφήνω τον αντίπαλό μου να κλείσει τετράγωνο στην επόμενη κίνηση". Είναι προφανές ότι η στρατηγική αυτή θα καταρρεύσει όταν όλα τα κουτιά έχουν αποκτήσει 2 από τις 4 ακμές τους. Ο παίκτης που θα παίξει μετά από αυτό το συμβάν θα τοποθετήσει μία 3η ακμή "χαρίζοντας" κουτί στον αντίπαλο.

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

Στο σχήμα βλέπουμε ότι για m=n=3 έχουμε κάτω όριο 4 ακμές και άνω 8 ακμές. Εάν τοποθετήσουμε U εξωτερικές ακμές αυτές καταμετρώνται ως μία για κάθε κουτί. Εάν τοποθετήσουμε X εσωτερικές ακμές αυτές καταμετρώνται ως μία για κάθε δύο κουτιά αφού κάθε μία ανήκει σε δύο κουτιά. Οπότε για T_mn κουτιά όταν θα έχουμε το συμβάν που λέγαμε θα ισχύει:

Αντικαθιστώντας από την (1) παίρνουμε:

Θέτω:

Α'_mnu = U+X = (m-1)(n-1) + U/2 [εξ. 5]

Ο νόμος που επιλέξαμε επιβάλλει U=άρτιος.

Μερικά παραδείγματα στο παρακάτω σχήμα.

Οι εναπομένουσες ακμές σε αυτή τη χρονική στιγμή του παιχνιδιού είναι:

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

Πρόβλημα: Η εξίσωση U+2X=2T_mn είναι "στατιστική" και υπονοεί ότι η μέση τιμή των ακμών ανά κουτί είναι 2. Όμως υπάρχει περίπτωση ένα κουτί να αδυνατεί να αποκτήσει 2 ακμές χωρίς ένα άλλο να αποκτήσει 3. Μια τέτοια περίπτωση φαίνεται στο σχήμα δεξιά.

Τα κουτιά με το κυκλάκι έχουν μια ακμή λιγότερη (δηλαδή μία). Αν αποπειραθούμε να δώσουμε 2 σε κάποιο εκ των δύο, κάποιο άλλο θα αποκτήσει 3, δηλαδή ο μέσος όρος θα είναι 2. Το πρόβλημα δεν εμφανίζεται για U=10 (δείτε τα βέλη). Αν, για U=12, δεν βάλουμε την παραπάνω ακμή (που θέσαμε) υστερεί κατά 1 της προβλεπόμενης τιμής.

Πράγματι αν σκεφτούμε ότι τα σχήματα με άρτιο αριθμό τελειών στις πλευρές έχουν συμμετρία ως προς νοητό κέντρο, ενώ αυτά με περιττό πλήθος τελειών ανά πλευρά έχουν συμμετρία ως προς υπαρκτό κέντρο και ως προς άξονα, διαπιστώνουμε πως στην πρώτη περίπτωση αν U/2 είναι άρτιος και Ε_mnu είναι περιττός, δεν υπάρχει περίπτωση κάθε ακμή να έχει το “ταίρι” της ως προς κέντρο, άρα το μοντέλο δεν αντιστοιχεί σε δεδομένη υλοποίηση. Πρέπει λοιπόν να δεχθούμε ότι εδώ είναι αδύνατη η συμπλήρωση 2 ακμών ανά τετράγωνο-κάποιο θα έχει 3 και κάποιο 1. Δηλαδή τα μεγέθη που ορίσαμε δεν έχουν εφαρμογή εδώ αφού πρέπει να μετράμ ήδη από μία ακμή πιο πριν. Έτσι, ειδικά εδώ, ορίζουμε τα μεγέθη:

Σε όλες τις άλλες περιπτώσεις λέμε απλά ότι μέσα σε E_mnu-1 ακμές θα κλείσουν (m-1)(n-1) κουτιά. Το “-1” αναφέρεται στο ότι ο πρώτος που τοποθετεί δεν κλείνει κανένα. Άρα, μένει να εξετάσουμε τη σειρά κλεισίματος των κουτιών, δηλαδή ποιος τοποθετεί πρώτος.

Αν παρατηρήσουμε το παράδειγμα U=2, Α’₃₃₂=5, θα δούμε ότι μπορεί το παιχνίδι να χωριστεί σε τρία ανεξάρτητα υποπαιχνίδια. Δύο 2x2 και ένα 2x3. Το τελευταίο όμως θέλει 3 ακμές ακόμα ενώ τα άλλα δύο έχουν δεδομένο νικητή. Άρα η σειρά τοποθετήσεως των ακμών έχει μεγάλη σημασία για το ποιος θα νικήσει. Τοποθετεί ο 2 πρώτος. Αν ξεκινήσει από το 3x2 να τοποθετεί, θα νικήσει, αν όχι, ή θα έρθει ισοπαλία ή θα χάσει. Η συγκεκριμένη περίπτωση γενικεύεται. Η τοποθέτηση των αρχικών ακμών θέτει “τείχη”, που χωρίζουν το παιχνίδι σε επιμέρους παιχνίδια και αυτό πρέπει εν γένει να λαμβάνεται υπόψιν. Άρα, είναι πολύ σημαντική η μελέτη και των τριών περιπτώσεων (I, II, III). Απλώς, θα μελετάμε κάθε περίπτωση σαν να είναι ολόκληρη ένα επι μέρους παιχνίδι.

Περίπτωση I: Τ_mn=περιττός

• Αν U/2=άρτιος τότε E΄_mnu=άρτιος, δηλαδή ο 2 κλείνει πρώτος, αφού ο 1 “προσφέρει” πρώτος ένα τετράγωνο. Ο 2 σε κάθε κίνηση θα κλείνει τετράγωνο ενώ ο 1 ίσως όχι πάντα. Μέσα σε E΄_mnu/2 κινήσεις ο 2 θα κλείσει ισάριθμα κουτιά, ενώ ο 1 τα υπόλοιπα. Ο 2 θα κερδίσει.
• Αν U/2=άρτιος τότε Emnu=άρτιος, δηλαδή ο 2 κλείνει πάλι πρώτος και στο σύνολο E_mnu/2 κουτιά με τον ίδιο συλλογισμό με πριν, ενώ ο 1 τα υπόλοιπα. Και πάλι ο 2 θα κερδίσει.

Περίπτωση II: Τ_mn=άρτιος

• Αν U/2=άρτιος τότε E_mnu=άρτιος άρα ο 2 κλείνει πρώτος και στο σύνολο Emnu/2 φορές κουτί. Όμως, η αξονική συμμετρία κάνει το θαύμα της! Αν η τελευταία τοποθέτηση γίνει σε εσωτερική ακμή (πράγμα πιθανό τώρα) ο 2 θα κλείσει E_mnu/2 +1 κουτιά και ο 1 τα υπόλοιπα. Η περίπτωση επιβάλλεται για m=n=3, U=4.
• Αν U/2=περιττός, τότε Ε_mnu=περιττός και ο 1 κλείνει πρώτος, ενώ ο 2 τελευταίος. Εδώ τα πράγματα για τον 2 είναι σκούρα, αφού ο 1 θα κλείνει σε κάθε κίνηση. Αν το παιχνίδι δεν σπάει σε υποπαιχνίδια, ο 2 θα φέρει το πολύ ισοπαλία.

Περίπτωση III: Τ_mn=άρτιος

• Aν U/2=άρτιος. τότε E_mnu=περιττός. Όμως Α_mn=περιττός επίσης, δηλαδή ο 2 κλείνει πρώτος και ο 1 τελευταίος. Εδώ κατά τα φαινόμενα ο 1 παίζει περισσότερες φορές οπότε μπορεί να ελέγξει το παιχνίδι. Ο 2 θα κλείνει σε κάθε κίνηση, δηλαδή θα κλείσει (E_mnu-1)/2 κουτιά και ο 1 τα υπόλοιπα.
• Αν U/2=περιττός τότε E_mnu=άρτιος. Όμοια, ο 2 κλείνει E_mnu/2 κουτιά και ο 1 τα υπόλοιπα. Αν το παιχνίδι διαιρείται σε υποπαιχνίδια τότε εξετάζουμε το καθένα από αυτά. Σημειώνουμε ότι η εξέταση των υποπαιχνιδιών είναι δύσκολη, αφού αυτά μπορεί να παίζονται σε σχήματα όπως αυτό του σχήματος, που δεν εμπίπτουν στην παραπάνω ανάλυση.

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

Κώστας Δρακάκης Ηλεκτρ.Μηχ.& Μηχ Η/Υ Άλλα άρθρα του συγγραφέα

Περιγραφή Προβλήματος

Μια πρώτη λύση