Förlorar du bara på Tetris för att du inte spelar optimalt eller gör misstag? Även med hur lång tid som helst att tänka på det kan en ogynnsam sekvens av stenar inte räddas. Det avgörande är fem smala körfält och ett udda nummer. Vi betraktar en spelplan med \(10\) kolumner och \(20\) rader utan urklipp (håll): Varje ny sten dras oberoende och jämnt fördelad från de sju tetrominoerna . Varje form består av fyra sammankopplade rutor. Hela avsnittet kan vara känt i förväg.
Det faktum att ett spel nästan säkert slutar betyder inte att alla tänkbara sekvenser av stenar tar slut. En ren sekvens av O-stenar kan spelas oändligt: fem rutor placerade bredvid varandra tar bort två rader och tömmer spelplanen. I 7-Bag innehåller varje slumpmässigt blandad påse alla sju former exakt en gång; vårt chansargument gäller inte detta. I How to Lose at Tetris visar Heidi Burgiel en sekvens som inte ens perfekt spel hjälper: \(S,Z,S,Z,\ldots\) .
S och Z är spegelbilder, inte olika rotationer av samma sten. Den medföljande förklaringen beskriver den geometriska idé som vi presenterar här som ett bevis genom motsägelse. Det uppenbara påståendet "vid någon tidpunkt dyker bara Z-stenar upp och ingen rad försvinner med dem" är fel. Bara fem identiska, vertikalt placerade S-stenar ger följande arrangemang på en initialt tom tavla. Samma bokstäver anger samma sten; Prickar markerar lediga utrymmen:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eDen mellersta raden är klar och raderad. Om du speglar arrangemanget får du samma motexempel för Z-stenar. Problemet är inte att radera enskilda rader, utan frågan om man kan kontrollera alla obalanser som uppstår över ett obegränsat antal stenar. Låt oss numrera kolumnerna från \(1\) till \(10\) . Med \(b_i\) anger vi det totala antalet av alla nya celler placerade i kolumn \(i\) , inklusive de som senare raderades.
\(h_i\) räknar horisontella S- eller Z-stenar med mittkolumnen \(i\) , \(v_i\) vertikala stenar i kolumnerna \(i\) och \(i+1\) . Räknarna registrerar spelets gång, inte bara den för närvarande synliga stapeln. En horisontell sten fördelar sina celler i förhållandet \(1,2,1\) över tre kolumner, en vertikal sten i förhållandet \(2,2\) i två kolumner. Båda spegelbilderna har samma kolumnbalans. Om du lägger ihop dessa bidrag för alla placeringar får du för varje kolumn:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Utanför brädet sätter vi alla räknare till \(0\) ; särskilt \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Denna kantkonvention hindrar balansen från att räkna stenar som skulle sträcka sig bortom kanten av spelplanen. Sådana placeringar är inte tillåtna i vår modell. Om den aktuella S/Z-sekvensen börjar på en redan fylld tavla, låt \(a_i\) vara de initialt upptagna cellerna och \(c_i\) de för närvarande upptagna cellerna i kolumn \(i\) . Efter \(R\) raderade rader är:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Så länge spelet körs är alla \(a_i,c_i\) mellan \(0\) och \(20\) . Därför gäller \(|b_i-b_j|\leq40\) . Om brädet är tomt från början räcker \(20\) . Varje raderad rad tar bort exakt en cell från varje kolumn. Detta är anledningen till att antalet raderade rader minskas när två kolumner jämförs, även om räknarna för de inställda cellerna fortsätter att växa. Du räknar ockuperade celler istället för stackhöjder; De två storlekarna skiljer sig åt när det kommer till hål. Om vi skriver den här gränsen generellt som \(D\) , resulterar den på vänster eller höger kant:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
För de inre kolumnparen lägger vi till två begränsade kolumnskillnader: \(b_4-b_3\) och \(b_2-b_1\) till vänster, \(b_7-b_8\) och \(b_9-b_{10}\) till höger. Efter att ha infogat kolumnbalansen tar räknarna däremellan ut varandra exakt. Detta lämnar bara icke-negativa bidrag på varje vänster sida, som är gemensamt avgränsade av \(2D\) . Detta ger oss också en övre gräns för respektive placeringsnummer för de två inre 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}$$
Om vi lägger till de fyra olikheterna räknas varje horisontell sten exakt en gång. De fyra typerna av tvärgående vertikala placeringar har också positiva koefficienter. De horisontella stenarna tar upp tre pelare och passar därför inte helt in i någon av de två pelare stigarna som behandlas senare. För de vertikala stenarna särskiljer vi spåren enligt den vänstra kolumnen. Eftersom alla räknare är icke-negativa kan inget av dessa bidrag annulleras av någon annan:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Horisontella placeringar och vertikala placeringar med rak vänster kolumn kan därför uppstå maximalt \(120\) gånger på en tom tavla eller \(240\) gånger på valfri förifylld tavla. Detta är en övre gräns, inte ett påstående om att det faktiskt kan uppnås. Hur som helst kan dessa undvikande drag inte användas oändligt ofta. Låt oss nu anta att du kan spela den alternerande sekvensen på obestämd tid.
Efter det sista av det ändliga antalet undvikande drag skulle endast vertikala placeringar i fem fasta banor vara möjliga: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Identiska former passar in i varandra i ett stegliknande mönster: botten möter den matchande toppen av den föregående stenen. Ändring från S till Ö eller vice versa lämnar ett gap en cell bred och två celler djup. Detaljen visar en Z-sten över en S-sten; båda "o" markerar mellanrummet:
.Z
ZZ
Zo
So
SS
.SEn annan vertikal sten i samma körfält kan inte fylla denna lucka: dess andra kolumn skulle kollidera med de närliggande ockuperade cellerna. Att ta bort rader hjälper inte heller så länge gapet är öppet, eftersom båda raderna inte är kompletta. En reparation kräver en av de redan uteslutna tvärbanorna eller horisontella placeringarna. Efter det sista undanflyktsdraget är sådana luckor permanenta. Ett oändligt antal nya, osammanhängande luckor kan inte uppstå på ett ändligt kort.
Som ett resultat kan det bara bli ett begränsat antal formförändringar på spåren. En från början tom körfält ändrar inte detta: din första S- eller Z-sten lämnar redan en enkolumnig lucka på golvet som inte kan stängas av ytterligare rent körfältsspel. I ett förmodat oändligt spel måste varje bana också innehålla ett oändligt antal stenar. Om ett körfält skulle förbli orört någon gång, skulle endast ett ändligt antal celler kunna inrymmas i de återstående körfälten på grund av de begränsade kolumnbalanserna.
Vi når därför en tidpunkt då alla fem körfälten är permanent upptagna och fast tilldelade en form. Från och med nu räknar vi \(t\) fler stenar och med \(n_j(t)\) numret i spår \(j\) . Var och en av dessa stenar bidrar med två celler till varje kolumn på dess spår. Eftersom radraderingar behandlar alla kolumner lika, förblir skillnaderna \(n_j(t)-n_k(t)\) begränsade. På lång sikt ska alla fem banorna rymma vardera en femtedel av stenarna:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Om \(k\) av de fem körfälten är reserverade för S-stenar bör deras andel vara runt \(k/5\) . Men i den alternerande sekvensen är det \(1/2\) : i varje prefix skiljer sig numren på S- och Z-stenarna med högst \(1\) . Uppdelningen av körfälten skulle behöva uppfylla båda delarna samtidigt. En andel på hälften kan dock inte representeras som summan av hela femtedelar. Det är här frekvensen av alternerande former och det udda antalet lika använda spår möts. Det skulle vara obligatoriskt:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Antalet körfält är ett heltal. Denna motsägelse gör slut på antagandet om ett oändligt spel. Argumentationen visar också varför tavlans bredd är en del av det: Med fyra tåg skulle en uppdelning i två S- och två Z-tåg inte uteslutas av denna motsättning. För det slumpmässiga beviset behöver vi en ändlig blocklängd \(N\) som leder till förlust oavsett det aktuella kortet. Enbart "Varje strategi förlorar någon gång" är inte tillräckligt.
Likformigheten följer av det ändliga antalet möjliga tillstånd. Efter varje genomförd placering finns det högst \(2^{200}\) beläggningsmönster. Det finns också information om huruvida S eller Z visas härnäst, det vill säga maximalt \(2^{201}\) tillstånd. Om du skulle överleva \(N=2^{201}\) stenar, skulle \(N+1\) tillstånden före och efter dessa drag få en upprepning. På grund av det identiska brädan och samma nästa form, skulle de lagliga dragen däremellan kunna upprepas hur många gånger som helst: det oändliga spelet utesluts bara.
Gränsen räknar också ouppnåeliga brädmönster och förutsäger inte praktisk spellängd. Burgiels finare geometriska räkning ger mindre gränser; här räcker det med en ändlig \(N\) . Den gäller för alla tillåtna initiala tilldelningar och båda faserna av S/Z-sekvensen. Låt oss dekomponera den oändliga slumpmässiga sekvensen i disjunkta block med längden \(N\) . Varje block är exakt den specificerade sekvensen \(S,Z,S,Z,\ldots\) med sannolikhet \(q=7^{-N}>0\) . Blocken är oberoende. Det är därför troligt att inget av de första \(m\) -blocken innehåller denna sekvens:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Så med sannolikhet \(1\) kommer ett dödligt block att dyka upp någon gång, om inte spelet tar slut innan dess. Detta gäller även med hur lång tid som helst att tänka på det och fullständig kunskap om hela sekvensen av stenar. Detta resulterar inte i en kort praktisk speltid. En ofokuserad, dålig start ensam betyder inte nederlag; överraskande comebacks är säkert möjliga. Så – bli inte avskräckt och njut av det tidlösa spelet.