Χάνεις στο Tetris μόνο επειδή δεν παίζεις βέλτιστα ή κάνεις λάθη; Ακόμη και αν έχετε χρόνο να το σκεφτείτε, μια δυσμενής σειρά λίθων δεν μπορεί να σωθεί. Ο καθοριστικός παράγοντας είναι πέντε στενές λωρίδες και ένας περιττός αριθμός. Θεωρούμε έναν αγωνιστικό χώρο με \(10\) στήλες και \(20\) σειρές χωρίς πρόχειρο (κρατήστε): Κάθε νέος λίθος σχεδιάζεται ανεξάρτητα και κατανέμεται εξίσου από τα επτά tetrominoes . Κάθε σχήμα αποτελείται από τέσσερα συνδεδεμένα τετράγωνα. Ολόκληρο το επεισόδιο μπορεί να είναι γνωστό εκ των προτέρων.
Το γεγονός ότι ένα παιχνίδι σχεδόν σίγουρα τελειώνει δεν σημαίνει ότι τελειώνει κάθε πιθανή ακολουθία πέτρες. Μια καθαρή ακολουθία O-stones μπορεί να παιχτεί ατελείωτα: πέντε τετράγωνα τοποθετημένα το ένα δίπλα στο άλλο διαγράφουν δύο σειρές και αδειάζουν τον πίνακα. Στο 7-Bag, κάθε τυχαία μικτή σακούλα περιέχει και τα επτά σχήματα ακριβώς μία φορά. Το τυχαίο επιχείρημά μας δεν ισχύει για αυτό. Στο How to Lose at Tetris, η Heidi Burgiel δείχνει μια σειρά που ακόμη και το τέλειο παιχνίδι δεν βοηθάει: \(S,Z,S,Z,\ldots\) .
Τα S και Z είναι κατοπτρικά είδωλα, όχι διαφορετικές περιστροφές της ίδιας πέτρας. Η συνοδευτική εξήγηση περιγράφει τη γεωμετρική ιδέα που παρουσιάζουμε εδώ ως απόδειξη με αντίφαση. Ο προφανής ισχυρισμός «κάποια στιγμή εμφανίζονται μόνο πέτρες Z και καμία σειρά δεν εξαφανίζεται μαζί τους» είναι λάθος. Μόλις πέντε πανομοιότυπες, κάθετα τοποθετημένες πέτρες S παρέχουν την ακόλουθη διάταξη σε μια αρχικά άδεια σανίδα. Τα ίδια γράμματα δείχνουν την ίδια πέτρα. Οι τελείες σηματοδοτούν ελεύθερα κενά:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eΗ μεσαία σειρά ολοκληρώθηκε και διαγράφηκε. Εάν αντικατοπτρίσετε τη διάταξη, θα έχετε το ίδιο αντιπαράδειγμα για τις πέτρες Z. Το πρόβλημα δεν είναι η διαγραφή μεμονωμένων σειρών, αλλά το ερώτημα εάν μπορείτε να ελέγξετε όλες τις ανισορροπίες που προκύπτουν σε έναν απεριόριστο αριθμό λίθων. Ας αριθμήσουμε τις στήλες από \(1\) έως \(10\) . Με \(b_i\) συμβολίζουμε τον συνολικό αριθμό όλων των νέων κελιών που τοποθετήθηκαν στη στήλη \(i\) , συμπεριλαμβανομένων αυτών που διαγράφηκαν αργότερα.
\(h_i\) μετράει οριζόντιες πέτρες S ή Z με μεσαία στήλη \(i\) , \(v_i\) κάθετες πέτρες στις στήλες \(i\) και \(i+1\) . Οι μετρητές καταγράφουν την πορεία του παιχνιδιού, όχι μόνο την ορατή στοίβα αυτή τη στιγμή. Μια οριζόντια πέτρα κατανέμει τα κελιά της με την αναλογία \(1,2,1\) σε τρεις στήλες, μια κάθετη πέτρα στην αναλογία \(2,2\) σε δύο στήλες. Και οι δύο κατοπτρικές εικόνες έχουν την ίδια ισορροπία στηλών. Εάν προσθέσετε αυτές τις συνεισφορές σε όλες τις τοποθετήσεις, θα λάβετε για κάθε στήλη:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Έξω από τον πίνακα ορίζουμε όλους τους μετρητές σε \(0\) ; συγκεκριμένα \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Αυτή η σύμβαση άκρων εμποδίζει την ισορροπία να μετρήσει πέτρες που θα εκτείνονταν πέρα από την άκρη του αγωνιστικού χώρου. Τέτοιες τοποθετήσεις δεν επιτρέπονται στο μοντέλο μας. Εάν η υπό εξέταση ακολουθία S/Z ξεκινά σε έναν ήδη γεμάτο πίνακα, έστω \(a_i\) τα αρχικά κατειλημμένα κελιά και \(c_i\) τα κατειλημμένα αυτήν τη στιγμή κελιά στη στήλη \(i\) . Μετά τις διαγραμμένες γραμμές \(R\) είναι:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Όσο το παιχνίδι εκτελείται, όλα τα \(a_i,c_i\) είναι μεταξύ \(0\) και \(20\) . Επομένως ισχύει \(|b_i-b_j|\leq40\) . Εάν ο πίνακας είναι αρχικά άδειος \(20\) είναι αρκετό. Κάθε διαγραμμένη σειρά αφαιρεί ακριβώς ένα κελί από κάθε στήλη. Αυτός είναι ο λόγος για τον οποίο ο αριθμός των διαγραμμένων σειρών μειώνεται κατά τη σύγκριση δύο στηλών, ακόμα κι αν οι μετρητές των συνόλου κελιών συνεχίσουν να αυξάνονται. Μετράτε τα κατειλημμένα κελιά αντί για τα ύψη στοίβας. Τα δύο μεγέθη διαφέρουν όταν πρόκειται για τρύπες. Αν γράψουμε αυτό το όριο γενικά ως \(D\) , προκύπτει στην αριστερή ή δεξιά άκρη:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Για τα εσωτερικά ζεύγη στηλών προσθέτουμε δύο περιορισμένες διαφορές στηλών: \(b_4-b_3\) και \(b_2-b_1\) στα αριστερά, \(b_7-b_8\) και \(b_9-b_{10}\) στα δεξιά. Μετά την εισαγωγή του υπολοίπου της στήλης, οι ενδιάμεσοι μετρητές αλληλοεξουδετερώνονται ακριβώς. Αυτό αφήνει μόνο μη αρνητικές συνεισφορές σε κάθε αριστερή πλευρά, οι οποίες οριοθετούνται από κοινού από \(2D\) . Αυτό μας δίνει επίσης ένα ανώτερο όριο για τους αντίστοιχους αριθμούς τοποθέτησης για τα δύο εσωτερικά ζεύγη:
$$\begin{aligned}2v_4+h_4+h_5&=(b_4-b_3)+(b_2-b_1)\\&\leq2D,\\2v_6+h_6+h_7&=(b_7-b_8)+(b_9-b_{10})\\&\leq2D.\end{aligned}$$
Αν προσθέσουμε τις τέσσερις ανισότητες, κάθε οριζόντιος λίθος μετράται ακριβώς μία φορά. Οι τέσσερις τύποι κάθετων τοποθετήσεων διασταύρωσης έχουν επίσης θετικούς συντελεστές. Οι οριζόντιες πέτρες καταλαμβάνουν τρεις κίονες και επομένως δεν ταιριάζουν πλήρως σε ένα από τα δίστηλα μονοπάτια που εξετάστηκαν αργότερα. Για τις κάθετες πέτρες διακρίνουμε τις ράγες σύμφωνα με την αριστερή στήλη. Δεδομένου ότι όλοι οι μετρητές είναι μη αρνητικοί, καμία από αυτές τις συνεισφορές δεν μπορεί να ακυρωθεί από άλλον:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Ως εκ τούτου, οι οριζόντιες και οι κάθετες τοποθετήσεις με ευθεία αριστερή στήλη μπορούν να πραγματοποιηθούν έως \(120\) φορές σε έναν κενό πίνακα ή \(240\) φορές σε οποιονδήποτε προγεμισμένο πίνακα. Αυτό είναι ένα ανώτερο όριο, όχι ένας ισχυρισμός ότι μπορεί πραγματικά να επιτευχθεί. Σε κάθε περίπτωση, αυτές οι κινήσεις υπεκφυγής δεν μπορούν να χρησιμοποιηθούν απείρως συχνά. Τώρα ας υποθέσουμε ότι θα μπορούσατε να παίξετε την εναλλασσόμενη ακολουθία επ' αόριστον.
Μετά τον τελευταίο από τον πεπερασμένο αριθμό των κινήσεων αποφυγής, μόνο κάθετες τοποθετήσεις σε πέντε σταθερές λωρίδες θα ήταν δυνατές: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Πανομοιότυπα σχήματα ταιριάζουν μεταξύ τους σε ένα μοτίβο που μοιάζει με σκαλοπάτι: το κάτω μέρος συναντά την ασορτί κορυφή της προηγούμενης πέτρας. Η αλλαγή από S σε Z ή αντίστροφα αφήνει ένα κενό πλάτος ενός κελιού και βάθος δύο κελιών. Η λεπτομέρεια δείχνει μια πέτρα Z πάνω από μια πέτρα S. και τα δύο «o» σηματοδοτούν το κενό:
.Z
ZZ
Zo
So
SS
.SΜια άλλη κάθετη πέτρα στην ίδια λωρίδα δεν μπορεί να καλύψει αυτό το κενό: η δεύτερη στήλη της θα συγκρούονταν με τα γειτονικά κατεχόμενα κελιά. Η διαγραφή σειρών δεν βοηθά ούτε όσο είναι ανοιχτό το κενό, γιατί και οι δύο σειρές δεν είναι πλήρεις. Μια επισκευή απαιτεί μία από τις ήδη αποκλεισμένες εγκάρσιες ή οριζόντιες τοποθετήσεις. Μετά την τελευταία κίνηση αποφυγής, τέτοια κενά είναι μόνιμα. Ένας άπειρος αριθμός νέων, ασύνδετων κενών δεν μπορεί να προκύψει σε έναν πεπερασμένο πίνακα.
Ως αποτέλεσμα, μπορεί να υπάρξει μόνο ένας πεπερασμένος αριθμός αλλαγών στη μορφή στις πίστες. Μια αρχικά άδεια λωρίδα δεν το αλλάζει αυτό: η πρώτη σας πέτρα S ή Z αφήνει ήδη ένα κενό μονής στήλης στο πάτωμα που δεν μπορεί να κλείσει με περαιτέρω καθαρό παιχνίδι λωρίδας. Σε ένα υποτιθέμενο άπειρο παιχνίδι, κάθε λωρίδα πρέπει επίσης να περιέχει έναν άπειρο αριθμό πετρών. Εάν μια λωρίδα παρέμενε ανέγγιχτη σε κάποιο σημείο, μόνο ένας πεπερασμένος αριθμός κυψελών θα μπορούσε να φιλοξενηθεί στις υπόλοιπες λωρίδες λόγω των περιορισμένων ισορροπιών στηλών.
Επομένως, φτάνουμε σε ένα χρονικό σημείο στο οποίο και οι πέντε λωρίδες είναι μόνιμα κατειλημμένες και σταθερά τοποθετημένες σε μια φόρμα. Από αυτό το σημείο και μετά μετράμε \(t\) περισσότερες πέτρες και με \(n_j(t)\) τον αριθμό στο κομμάτι \(j\) . Κάθε μία από αυτές τις πέτρες συνεισφέρει δύο κελιά σε κάθε στήλη της διαδρομής της. Επειδή οι διαγραφές σειρών αντιμετωπίζουν όλες τις στήλες εξίσου, οι διαφορές \(n_j(t)-n_k(t)\) παραμένουν περιορισμένες. Μακροπρόθεσμα, και οι πέντε λωρίδες πρέπει να χωρούν το ένα πέμπτο των λίθων:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Εάν \(k\) από τις πέντε λωρίδες είναι δεσμευμένες για S-stones, το μερίδιό τους θα πρέπει να είναι περίπου \(k/5\) . Ωστόσο, στην εναλλασσόμενη ακολουθία είναι \(1/2\) : σε κάθε πρόθεμα οι αριθμοί των λίθων S και Z διαφέρουν το πολύ κατά \(1\) . Η διαίρεση των λωρίδων θα έπρεπε να εκπληρώνει και τα δύο μέρη ταυτόχρονα. Ωστόσο, ένα μερίδιο του μισού δεν μπορεί να αναπαρασταθεί ως άθροισμα ολόκληρων πέμπτων. Εδώ ενώνονται η συχνότητα των εναλλασσόμενων μορφών και ο περιττός αριθμός εξίσου χρησιμοποιούμενων κομματιών. Αυτό θα ήταν υποχρεωτικό:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Ο αριθμός των λωρίδων είναι ακέραιος. Αυτή η αντίφαση τερματίζει την υπόθεση ενός άπειρου παιχνιδιού. Το επιχείρημα δείχνει επίσης γιατί το πλάτος του πίνακα είναι μέρος του: Με τέσσερα τρένα, μια διαίρεση σε δύο συρμούς S και δύο Z δεν θα αποκλείεται από αυτήν την αντίφαση. Για την τυχαία απόδειξη χρειαζόμαστε ένα πεπερασμένο μήκος μπλοκ \(N\) που οδηγεί σε απώλεια ανεξάρτητα από την τρέχουσα πλακέτα. Το «κάθε στρατηγική χάνει κάποια στιγμή» από μόνο του δεν αρκεί.
Η ομοιομορφία προκύπτει από τον πεπερασμένο αριθμό των πιθανών καταστάσεων. Μετά από κάθε ολοκληρωμένη τοποθέτηση, υπάρχουν το πολύ \(2^{200}\) μοτίβα πληρότητας. Υπάρχουν επίσης πληροφορίες σχετικά με το εάν το S ή το Z εμφανίζεται στη συνέχεια, δηλαδή το μέγιστο των καταστάσεων \(2^{201}\) . Εάν επρόκειτο να επιβιώσετε από πέτρες \(N=2^{201}\) , οι καταστάσεις \(N+1\) πριν και μετά από αυτές τις κινήσεις θα είχαν επανάληψη. Λόγω του ίδιου πίνακα και του ίδιου επόμενου σχήματος, οι νόμιμες κινήσεις στο μεταξύ θα μπορούσαν να επαναληφθούν πολλές φορές: το άπειρο παιχνίδι μόλις εξαιρέθηκε.
Το όριο μετράει επίσης τα απρόσιτα μοτίβα του πίνακα και δεν προβλέπει την πρακτική διάρκεια του παιχνιδιού. Η λεπτότερη γεωμετρική μέτρηση του Burgiel δίνει μικρότερα όρια. εδώ αρκεί ένα πεπερασμένο \(N\) . Ισχύει για όλες τις επιτρεπόμενες αρχικές εκχωρήσεις και για τις δύο φάσεις της ακολουθίας S/Z. Ας αποσυνθέσουμε την άπειρη τυχαία ακολουθία σε ασύνδετα μπλοκ μήκους \(N\) . Κάθε μπλοκ είναι ακριβώς η καθορισμένη ακολουθία \(S,Z,S,Z,\ldots\) με πιθανότητα \(q=7^{-N}>0\) . Τα μπλοκ είναι ανεξάρτητα. Είναι επομένως πιθανό ότι κανένα από τα πρώτα μπλοκ \(m\) δεν περιέχει αυτήν την ακολουθία:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Έτσι, με πιθανότητα \(1\) θα εμφανιστεί ένα θανατηφόρο μπλοκ κάποια στιγμή, εκτός και αν το παιχνίδι τελειώσει πριν από τότε. Αυτό ισχύει επίσης για κάθε χρόνο για να το σκεφτείτε και πλήρη γνώση ολόκληρης της σειράς των λίθων. Αυτό δεν οδηγεί σε σύντομο πρακτικό χρόνο παιχνιδιού. Ένα μη επικεντρωμένο, κακό ξεκίνημα από μόνο του δεν σημαίνει ήττα. εκπληκτικές επιστροφές είναι σίγουρα πιθανές. Επομένως – μην αποθαρρύνεστε και απολαύστε το διαχρονικό παιχνίδι.