Csak azért veszít a Tetrisben, mert nem játszik optimálisan, vagy hibázik? Még ha gondolkozunk is rajta, egy kedvezőtlen kősort nem lehet megmenteni. A döntő az öt keskeny sáv és a páratlan szám. A játékteret \(10\) oszlopokkal és \(20\) sorokkal vágólap nélkül tekintjük (tartás): Minden új követ egymástól függetlenül és egyenlően elosztva a hét tetrominóból húzunk. Mindegyik alakzat négy összefüggő négyzetből áll. Lehet, hogy a teljes epizód előre ismert.
Az a tény, hogy egy játék szinte biztosan véget ér, nem jelenti azt, hogy a kövek minden elképzelhető sorozata véget ér. Az O-kövek tiszta sorozata végtelenségig játszható: öt egymás mellé helyezett négyzet töröl két sort és üríti ki a táblát. A 7-Bag-ban minden véletlenszerűen kevert zacskó pontosan egyszer tartalmazza mind a hét formát; esélyérvünk erre nem vonatkozik. A How to Lose at Tetrisben Heidi Burgiel bemutat egy sorozatot, amin még a tökéletes játék sem segít: \(S,Z,S,Z,\ldots\) .
S és Z tükörképei, nem ugyanazon kő különböző forgatásai. A mellékelt magyarázat leírja azt a geometriai elképzelést, amelyet itt ellentmondásos bizonyítékként mutatunk be. Az a nyilvánvaló állítás, hogy „valamikor csak Z kövek jelennek meg, és egyetlen sor sem tűnik el velük” téves. Mindössze öt egyforma, függőlegesen elhelyezett S-kő biztosítja a következő elrendezést egy kezdetben üres táblán. Ugyanazok a betűk ugyanazt a követ jelölik; Pontok jelölik a szabad helyeket:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eA középső sor elkészült és törölve. Ha tükrözi az elrendezést, ugyanazt az ellenpéldát kapja a Z-kövekre. A probléma nem az egyes sorok törlése, hanem az a kérdés, hogy képes-e szabályozni a korlátlan számú kövön fellépő egyensúlytalanságot. Számozzuk meg az oszlopokat \(1\) -től \(10\) -ig. A \(b_i\) a \(i\) oszlopban elhelyezett összes új cella teljes számát jelöli, beleértve a később törölteket is.
\(h_i\) vízszintes S vagy Z köveket számol \(i\) középső oszloppal, \(v_i\) függőleges köveket az \(i\) és \(i+1\) oszlopokban. A számlálók a játék menetét rögzítik, nem csak a pillanatnyilag látható stacket. Egy vízszintes kő \(1,2,1\) arányban osztja el celláit három oszlopban, egy függőleges kő \(2,2\) arányban két oszlopban. Mindkét tükörképen ugyanaz az oszlopegyensúly. Ha összeadja ezeket a hozzájárulásokat az összes elhelyezéshez, akkor minden oszlopra megkapja:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
A táblán kívül minden számlálót \(0\) értékre állítunk; különösen \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Ez az élkonvenció megakadályozza, hogy a mérleg olyan köveket számoljon, amelyek túlnyúlnának a játéktér szélén. Az ilyen elhelyezések nem engedélyezettek a modellünkben. Ha a vizsgált S/Z sorozat egy már kitöltött táblán kezdődik, legyen \(a_i\) az eredetileg foglalt cellák, és \(c_i\) a jelenleg foglalt cellák az \(i\) oszlopban. \(R\) után a törölt sorok az:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Amíg a játék fut, az összes \(a_i,c_i\) \(0\) és \(20\) között van. Ezért \(|b_i-b_j|\leq40\) érvényes. Ha a tábla kezdetben üres \(20\) elegendő. Minden törölt sor pontosan egy cellát vesz el minden oszlopból. Ezért csökken a törölt sorok száma két oszlop összehasonlításakor, még akkor is, ha a beállított cellák számlálói tovább nőnek. A veremmagasságok helyett a foglalt cellákat számolja; A két méret különbözik a lyukak tekintetében. Ha ezt a határértéket általában \(D\) -ként írjuk le, akkor a bal vagy a jobb szélre kerül:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
A belső oszloppárokhoz két korlátozott oszlopkülönbséget adunk: \(b_4-b_3\) és \(b_2-b_1\) a bal oldalon, \(b_7-b_8\) és \(b_9-b_{10}\) a jobb oldalon. Az oszlopegyenleg beillesztése után a között lévő számlálók pontosan kioltják egymást. Ez csak nem negatív hozzájárulásokat hagy a bal oldalon, amelyeket együttesen \(2D\) határol. Ez ad egy felső határt is a két belső pár megfelelő elhelyezési számára:
$$\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}$$
Ha összeadjuk a négy egyenlőtlenséget, minden vízszintes követ pontosan egyszer számol. A keresztirányú függőleges elhelyezés négy típusának pozitív együtthatója is van. A vízszintes kövek három oszlopot foglalnak el, ezért nem illeszkednek teljesen a későbbiekben tárgyalt kétoszlopos pályák egyikébe. A függőleges köveknél a bal oldali oszlop szerint különítjük el a nyomokat. Mivel az összes számláló nem negatív, ezen hozzájárulások egyike sem törölhető mással:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
A vízszintes és függőleges elhelyezések egyenes bal oldali oszloppal ezért legfeljebb \(120\) alkalommal fordulhatnak elő üres táblán vagy \(240\) alkalommal bármely előre kitöltött táblán. Ez egy felső korlát, nem pedig annak állítása, hogy ez valóban elérhető. Mindenesetre ezeket a kitérő mozdulatokat nem lehet végtelenül gyakran használni. Most tegyük fel, hogy a váltakozó sorozatot a végtelenségig játszhatja.
A véges számú kitérő mozgás közül az utolsó után már csak függőleges elhelyezés lehetséges öt rögzített sávban: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Lépésszerűen illeszkednek egymásba az azonos formák: az alja találkozik az előző kő hozzáillő tetejével. S-ről Z-re vagy fordítva váltva egy cella széles és két cella mély rést hagy. A részleten Z-kő látható egy S-kő felett; mindkét „o” a rést jelöli:
.Z
ZZ
Zo
So
SS
.SEgy másik függőleges kő ugyanabban a sávban ezt a hiányt nem tudja betölteni: a második oszlopa ütközne a szomszédos elfoglalt cellákkal. A sorok törlése sem segít, amíg a rés nyitva van, mert mindkét sor nem teljes. A javításhoz szükség van a már kizárt keresztirányú vagy vízszintes elhelyezésekre. Az utolsó kitérő mozdulat után az ilyen hézagok állandóak. Egy véges táblán nem keletkezhet végtelen számú új, diszjunkt rés.
Ebből kifolyólag a pályákon csak véges számú formaváltozás történhet. Egy kezdetben üres sáv ezen nem változtat: az első S vagy Z kő már egy oszlopos rést hagy a padlón, amelyet további tiszta sávjátékkal nem lehet lezárni. Egy állítólag végtelen játékban minden sávban végtelen számú kőnek is kell lennie. Ha egy sáv valamikor érintetlen maradna, a korlátozott oszlopegyensúly miatt a fennmaradó sávokban csak véges számú cella férne el.
Ezért elérkezünk ahhoz az időponthoz, amikor mind az öt sáv állandóan foglalt, és szilárdan egy űrlaphoz van rendelve. Ettől kezdve még \(t\) követ számolunk és \(n_j(t)\) -vel a \(j\) sávban lévő számot. Ezen kövek mindegyike két cellával járul hozzá a pálya minden oszlopához. Mivel a sortörlések minden oszlopot egyformán kezelnek, a \(n_j(t)-n_k(t)\) különbségek korlátozottak maradnak. Hosszú távon mind az öt sávban kell tartani a kövek egyötödét:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Ha az öt sávból \(k\) az S-kövek számára van fenntartva, akkor arányuk \(k/5\) körül legyen. A váltakozó sorozatban azonban ez \(1/2\) : minden előtagban az S és Z kövek száma legfeljebb \(1\) -el tér el. A sávok felosztásának mindkét részt egyszerre kellene teljesítenie. A feles részesedést azonban nem lehet egész ötödök összegeként ábrázolni. Itt jön össze a váltakozó formák gyakorisága és az egyformán használt számok páratlan száma. Ez kötelező lenne:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
A sávok száma egész szám. Ez az ellentmondás véget vet a végtelen játék feltételezésének. Az érvelésből az is kiderül, hogy miért része ennek a táblaszélességnek: Négy vonat esetén ez az ellentmondás nem zárná ki a két S és két Z szerelvényre való felosztást. A véletlenszerű bizonyításhoz szükségünk van egy véges blokkhosszra \(N\) , amely az aktuális táblától függetlenül veszteséghez vezet. „Minden stratégia veszít egy ponton” önmagában nem elég.
Az egységesség a lehetséges állapotok véges számából következik. Minden egyes befejezett elhelyezés után legfeljebb \(2^{200}\) foglaltsági minták vannak. Arra is van információ, hogy S vagy Z jelenik-e meg ezután, azaz legfeljebb \(2^{201}\) állapotok. Ha túlélnéd \(N=2^{201}\) köveket, akkor a \(N+1\) állapotok e lépések előtt és után ismétlődnek. Az azonos tábla és ugyanaz a következő alakzat miatt a köztes lépések akárhányszor megismételhetők: a végtelen játék kizárva.
A limit az elérhetetlen táblamintákat is számolja, és nem jósolja meg a gyakorlati játék hosszát. Burgiel finomabb geometriai számlálása kisebb határokat ad; itt elég egy véges \(N\) . Ez az összes megengedett kezdeti hozzárendelésre és az S/Z sorozat mindkét fázisára vonatkozik. Bontsuk fel a végtelen véletlen sorozatot \(N\) hosszúságú diszjunkt blokkra. Minden blokk pontosan a megadott sorozat \(S,Z,S,Z,\ldots\) \(q=7^{-N}>0\) valószínűséggel. A blokkok függetlenek. Ezért valószínű, hogy az első \(m\) blokkok egyike sem tartalmazza ezt a sorozatot:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Tehát \(1\) valószínűséggel egy halálos blokk jelenik meg valamikor, hacsak a játék nem ér véget előtte. Ez vonatkozik a gondolkodásra és a következmények teljes ismeretére is. Ez nem eredményez rövid gyakorlati játékidőt, és a rossz kezdés önmagában nem jelent vereséget: A következő animáció öt előre kiszámított vegyes sorozatot mutat be, amelyek mindegyike kilenc változatlan torony elhelyezés után ér egy üres táblához. Ő nem egy univerzális Tetris bot.