Verlies je bij Tetris alleen maar omdat je niet optimaal speelt of fouten maakt? Zelfs met enige tijd om erover na te denken, kan een ongunstige reeks stenen niet worden gered. Doorslaggevend zijn vijf smalle rijstroken en een oneven aantal. We beschouwen een speelveld met \(10\) kolommen en \(20\) rijen zonder klembord (hold): Elke nieuwe steen wordt onafhankelijk en gelijkmatig verdeeld uit de zeven tetromino's getrokken. Elke vorm bestaat uit vier verbonden vierkanten. De hele aflevering is mogelijk van tevoren bekend.
Het feit dat een spel vrijwel zeker eindigt, betekent niet dat elke denkbare reeks stenen eindigt. Een pure reeks O-stenen kan eindeloos worden gespeeld: vijf naast elkaar geplaatste vierkanten schrappen twee rijen en maken het bord leeg. In 7-Bag bevat elke willekeurig gemengde zak alle zeven vormen precies één keer; ons toevalsargument is hierop niet van toepassing. In How to Lose at Tetris laat Heidi Burgiel een reeks zien waar zelfs perfect spel niet helpt: \(S,Z,S,Z,\ldots\) .
S en Z zijn spiegelbeelden, geen verschillende rotaties van dezelfde steen. De begeleidende uitleg beschrijft het geometrische idee dat we hier presenteren als een bewijs door tegenspraak. De voor de hand liggende bewering “op een gegeven moment verschijnen alleen Z-stenen en verdwijnt er geen enkele rij mee” is onjuist. Slechts vijf identieke, verticaal geplaatste S-stenen zorgen voor de volgende opstelling op een aanvankelijk leeg bord. Dezelfde letters duiden op dezelfde steen; Punten markeren vrije spaties:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eDe middelste rij is voltooid en verwijderd. Als je de opstelling spiegelt, krijg je hetzelfde tegenvoorbeeld voor Z-stenen. Het probleem is niet het verwijderen van individuele rijen, maar de vraag of je alle onevenwichtigheden die over een onbeperkt aantal stenen ontstaan, kunt beheersen. Laten we de kolommen nummeren van \(1\) tot \(10\) . Met \(b_i\) geven we het totale aantal nieuwe cellen aan die in kolom \(i\) zijn geplaatst, inclusief de cellen die later zijn verwijderd.
\(h_i\) telt horizontale S- of Z-stenen met middelste kolom \(i\) , \(v_i\) verticale stenen in kolommen \(i\) en \(i+1\) . De tellers registreren het verloop van het spel, niet alleen de momenteel zichtbare stapel. Een horizontale steen verdeelt zijn cellen in de verhouding \(1,2,1\) over drie kolommen, een verticale steen in de verhouding \(2,2\) over twee kolommen. Beide spiegelbeelden hebben hetzelfde kolomevenwicht. Als u deze bijdragen voor alle plaatsingen bij elkaar optelt, krijgt u voor elke kolom:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Buiten het bord zetten we alle tellers op \(0\) ; in het bijzonder \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Deze randconventie voorkomt dat de balans stenen telt die buiten de rand van het speelveld zouden reiken. Dergelijke plaatsingen zijn in ons model niet toegestaan. Als de S/Z-reeks in kwestie begint op een reeds gevuld bord, laat dan \(a_i\) de aanvankelijk bezette cellen zijn en \(c_i\) de momenteel bezette cellen in kolom \(i\) . Na \(R\) verwijderde rijen is:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Zolang het spel actief is, liggen alle \(a_i,c_i\) tussen \(0\) en \(20\) . Daarom is \(|b_i-b_j|\leq40\) van toepassing. Als het bord aanvankelijk leeg is \(20\) voldoende. Elke verwijderde rij neemt precies één cel uit elke kolom weg. Dit is de reden waarom het aantal verwijderde rijen wordt verminderd bij het vergelijken van twee kolommen, zelfs als de tellers van de ingestelde cellen blijven groeien. Je telt bezette cellen in plaats van stapelhoogtes; De twee maten verschillen qua gaten. Als we deze limiet in het algemeen schrijven als \(D\) , resulteert dit in de linker- of rechterrand:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Voor de binnenste kolomparen voegen we twee beperkte kolomverschillen toe: \(b_4-b_3\) en \(b_2-b_1\) aan de linkerkant, \(b_7-b_8\) en \(b_9-b_{10}\) aan de rechterkant. Na het invoeren van het kolomsaldo heffen de tussenliggende tellers elkaar precies op. Hierdoor blijven er aan elke linkerkant alleen niet-negatieve bijdragen over, die gezamenlijk worden begrensd door \(2D\) . Dit geeft ons ook een bovengrens voor de respectievelijke plaatsingsnummers voor de twee binnenste paren:
$$\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}$$
Als we de vier ongelijkheden optellen, wordt elke horizontale steen precies één keer geteld. De vier typen verticale plaatsingen over het spoor hebben ook positieve coëfficiënten. De horizontale stenen nemen drie kolommen in beslag en passen daarom niet volledig in een van de later besproken tweekolomspaden. Voor de verticale stenen onderscheiden we de sporen volgens de linkerkolom. Omdat alle tellers niet negatief zijn, kan geen van deze bijdragen door een ander worden geannuleerd:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Horizontale plaatsingen en verticale plaatsingen met een rechte linkerkolom kunnen daarom maximaal \(120\) keer voorkomen op een leeg bord of \(240\) keer op elk vooraf gevuld bord. Dit is een bovengrens, geen claim dat deze daadwerkelijk kan worden bereikt. In ieder geval kunnen deze ontwijkende bewegingen niet oneindig vaak worden gebruikt. Laten we nu aannemen dat je de afwisselende reeks voor onbepaalde tijd kunt spelen.
Na de laatste van het eindige aantal ontwijkende zetten zouden alleen verticale plaatsingen in vijf vaste rijstroken mogelijk zijn: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Identieke vormen passen in een trapsgewijs patroon in elkaar: de onderkant ontmoet de bijpassende bovenkant van de vorige steen. Bij het wisselen van S naar Z of andersom ontstaat er een opening van één cel breed en twee cellen diep. Het detail toont een Z-steen over een S-steen; beide “o” markeren de opening:
.Z
ZZ
Zo
So
SS
.SEen andere verticale steen in dezelfde baan kan dit gat niet opvullen: de tweede kolom zou in botsing komen met de aangrenzende bezette cellen. Rijen verwijderen helpt ook niet zolang het gat open is, omdat beide rijen niet compleet zijn. Voor een reparatie is een van de reeds uitgesloten cross-track of horizontale plaatsingen vereist. Na de laatste ontwijkende zet zijn dergelijke gaten permanent. Op een eindig bord kunnen geen oneindig aantal nieuwe, onsamenhangende hiaten ontstaan.
Als gevolg hiervan kunnen er slechts een eindig aantal vormveranderingen op de sporen plaatsvinden. Een aanvankelijk lege baan verandert daar niets aan: je eerste S- of Z-steen laat al een gat van één kolom op de vloer achter dat niet kan worden gedicht door verder puur baanspel. In een zogenaamd oneindig spel moet elke baan ook een oneindig aantal stenen bevatten. Als een rijstrook op een gegeven moment onaangeroerd zou blijven, zou vanwege de beperkte kolombalansen slechts een eindig aantal cellen in de resterende rijstroken kunnen worden ondergebracht.
We bereiken dus een punt waarop alle vijf de rijstroken permanent bezet zijn en stevig aan een formulier zijn toegewezen. Vanaf dit punt tellen we \(t\) meer stenen en met \(n_j(t)\) het nummer in spoor \(j\) . Elk van deze stenen draagt twee cellen bij aan elke kolom van zijn spoor. Omdat rijverwijderingen alle kolommen gelijk behandelen, blijven de verschillen \(n_j(t)-n_k(t)\) beperkt. Op de lange termijn moeten alle vijf de banen elk een vijfde van de stenen bevatten:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Als \(k\) van de vijf rijstroken gereserveerd is voor S-stenen, zou hun aandeel rond \(k/5\) moeten liggen. In de afwisselende reeks is het echter \(1/2\) : in elk voorvoegsel verschillen de nummers van de S- en Z-stenen maximaal met \(1\) . De verdeling van de rijstroken zou beide delen tegelijkertijd moeten vervullen. Een deel van de helft kan echter niet worden weergegeven als de som van hele vijfde. Hier komen de frequentie van afwisselende vormen en het oneven aantal even gebruikte nummers samen. Dat zou verplicht zijn:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Het aantal rijstroken is een geheel getal. Deze tegenstrijdigheid maakt een einde aan de aanname van een oneindig spel. Uit de argumentatie blijkt ook waarom de bordbreedte erbij hoort: bij vier treinen zou een opdeling in twee S- en twee Z-treinen door deze tegenstrijdigheid niet worden uitgesloten. Voor het willekeurige bewijs hebben we een eindige bloklengte \(N\) nodig die tot verlies leidt, ongeacht het huidige bord. ‘Elke strategie verliest op een gegeven moment’ alleen is niet genoeg.
De uniformiteit volgt uit het eindige aantal mogelijke toestanden. Na elke voltooide plaatsing zijn er maximaal \(2^{200}\) bezettingspatronen. Er is ook informatie over of S of Z daarna verschijnt, d.w.z. maximaal \(2^{201}\) toestanden. Als je \(N=2^{201}\) stenen zou overleven, zouden de \(N+1\) toestanden voor en na deze zetten een herhaling hebben. Vanwege het identieke bord en dezelfde volgende vorm zouden de legale zetten daartussen een onbeperkt aantal keren herhaalbaar zijn: het oneindige spel was gewoon uitgesloten.
De limiet telt ook onbereikbare bordpatronen en voorspelt geen praktische spelduur. Burgiels fijnere geometrische telling geeft kleinere grenzen; hier volstaat een eindige \(N\) . Het geldt voor alle toegestane initiële toewijzingen en beide fasen van de S/Z-reeks. Laten we de oneindige willekeurige reeks ontleden in onsamenhangende blokken met de lengte \(N\) . Elk blok heeft exact de opgegeven reeks \(S,Z,S,Z,\ldots\) met waarschijnlijkheid \(q=7^{-N}>0\) . De blokken zijn onafhankelijk. Het is daarom waarschijnlijk dat geen van de eerste \(m\) blokken deze reeks bevat:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Dus met waarschijnlijkheid \(1\) zal er op een gegeven moment een dodelijk blok verschijnen, tenzij het spel eerder eindigt. Dit geldt ook voor enige tijd om erover na te denken en volledige kennis van de hele reeks stenen. Dit resulteert niet in een korte praktische speeltijd. Een ongerichte, slechte start alleen betekent niet dat er een nederlaag is; verrassende comebacks zijn zeker mogelijk. Dus wees niet ontmoedigd en geniet van het tijdloze spel.