Taber du kun hos Tetris, fordi du ikke spiller optimalt eller laver fejl? Selv med nogen tid til at tænke over det, kan en ugunstig sekvens af sten ikke reddes. Det afgørende er fem smalle baner og et ulige tal. Vi betragter et spillefelt med \(10\) kolonner og \(20\) rækker uden et udklipsholder (hold): Hver ny sten tegnes uafhængigt og ligeligt fordelt fra de syv tetrominoer . Hver form består af fire forbundne firkanter. Hele episoden kan være kendt på forhånd.
Det faktum, at et spil næsten helt sikkert slutter, betyder ikke, at enhver tænkelig række af sten slutter. En ren sekvens af O-sten kan spilles uendeligt: Fem felter placeret ved siden af hinanden sletter to rækker og tømmer brættet. I 7-Bag indeholder hver tilfældigt blandet pose alle syv former præcis én gang; vores chance argument gælder ikke for dette. I How to Lose at Tetris viser Heidi Burgiel en sekvens, som selv perfekt spil ikke hjælper: \(S,Z,S,Z,\ldots\) .
S og Z er spejlbilleder, ikke forskellige rotationer af den samme sten. Den medfølgende forklaring beskriver den geometriske idé, som vi præsenterer her som et modsigelsesbevis. Den åbenlyse påstand "på et tidspunkt dukker kun Z-sten op, og ingen række forsvinder med dem" er forkert. Kun fem identiske, lodret placerede S-sten giver følgende arrangement på en oprindelig tom bræt. De samme bogstaver angiver den samme sten; Prikker markerer ledige pladser:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eDen midterste række er færdig og slettet. Hvis du spejler arrangementet, får du det samme modeksempel for Z-sten. Problemet er ikke at slette enkelte rækker, men spørgsmålet om, hvorvidt du kan kontrollere alle de ubalancer, der opstår på tværs af et ubegrænset antal sten. Lad os nummerere kolonnerne fra \(1\) til \(10\) . Med \(b_i\) angiver vi det samlede antal af alle nye celler placeret i kolonne \(i\) , inklusive dem, der senere er slettet.
\(h_i\) tæller vandrette S- eller Z-sten med midtersøjle \(i\) , \(v_i\) lodrette sten i kolonnerne \(i\) og \(i+1\) . Tællerne registrerer spillets gang, ikke kun den aktuelt synlige stak. En vandret sten fordeler sine celler i forholdet \(1,2,1\) over tre søjler, en lodret sten i forholdet \(2,2\) i to søjler. Begge spejlbilleder har samme søjlebalance. Hvis du lægger disse bidrag sammen på tværs af alle placeringer, får du for hver kolonne:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Uden for brættet sætter vi alle tællere til \(0\) ; især \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Denne kantkonvention forhindrer balancen i at tælle sten, der ville strække sig ud over kanten af spillefeltet. Sådanne placeringer er ikke tilladt i vores model. Hvis S/Z-sekvensen under overvejelse begynder på en allerede fyldt tavle, lad \(a_i\) være de oprindeligt besatte celler og \(c_i\) de aktuelt besatte celler i kolonne \(i\) . Efter \(R\) slettede rækker er:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Så længe spillet kører, er alle \(a_i,c_i\) mellem \(0\) og \(20\) . Derfor gælder \(|b_i-b_j|\leq40\) . Hvis brættet i starten er tomt \(20\) nok. Hver slettet række fjerner nøjagtig én celle fra hver kolonne. Dette er grunden til, at antallet af slettede rækker reduceres, når man sammenligner to kolonner, selvom tællerne i de indstillede celler fortsætter med at vokse. Du tæller besatte celler i stedet for stakhøjder; De to størrelser adskiller sig, når det kommer til huller. Hvis vi generelt skriver denne grænse som \(D\) , resulterer det på venstre eller højre 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.$$
For de indre kolonnepar tilføjer vi to begrænsede kolonneforskelle: \(b_4-b_3\) og \(b_2-b_1\) til venstre, \(b_7-b_8\) og \(b_9-b_{10}\) til højre. Efter indsættelse af kolonnebalancen ophæver tællerne i mellem nøjagtigt hinanden. Dette efterlader kun ikke-negative bidrag på hver venstre side, som er fælles afgrænset af \(2D\) . Dette giver os også en øvre grænse for de respektive placeringstal for de to indre par:
$$\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}$$
Tilføjer vi de fire uligheder, tælles hver vandret sten præcis én gang. De fire typer af tværgående vertikale placeringer har også positive koefficienter. De vandrette sten fylder tre søjler og passer derfor ikke helt ind i en af de to-søjlede stier, der senere behandles. For de lodrette sten skelner vi sporene i henhold til venstre kolonne. Da alle tællere er ikke-negative, kan ingen af disse bidrag annulleres af en anden:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Vandrette placeringer og lodrette placeringer med lige venstre kolonne kan derfor maksimalt forekomme \(120\) gange på en tom tavle eller \(240\) gange på en hvilken som helst forudfyldt tavle. Dette er en øvre grænse, ikke en påstand om, at det rent faktisk kan opnås. Under alle omstændigheder kan disse undvigende træk ikke bruges uendeligt ofte. Lad os nu antage, at du kan spille den vekslende sekvens på ubestemt tid.
Efter det sidste af det endelige antal undvigende træk ville kun lodrette placeringer i fem faste baner være mulige: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Identiske former passer ind i hinanden i et trinlignende mønster: Bunden møder den matchende top af den forrige sten. Skift fra S til Z eller omvendt efterlader et hul en celle bred og to celler dyb. Detaljen viser en Z-sten over en S-sten; begge "o" markerer mellemrummet:
.Z
ZZ
Zo
So
SS
.SEn anden lodret sten i samme bane kan ikke udfylde dette hul: dens anden søjle ville kollidere med de besatte naboceller. Det hjælper heller ikke at slette rækker, så længe mellemrummet er åbent, fordi begge rækker ikke er fuldstændige. En reparation kræver en af de allerede udelukkede cross-track eller vandrette placeringer. Efter det sidste undvigende træk er sådanne huller permanente. Et uendeligt antal nye, usammenhængende huller kan ikke opstå på et begrænset bord.
Som følge heraf kan der kun være et begrænset antal formændringer på sporene. En indledningsvis tom bane ændrer ikke dette: din første S- eller Z-sten efterlader allerede et enkelt-søjle-gab på gulvet, som ikke kan lukkes af yderligere rent banespil. I et angiveligt uendeligt spil skal hver bane også indeholde et uendeligt antal sten. Hvis en bane skulle forblive uberørt på et tidspunkt, kunne kun et begrænset antal celler rummes i de resterende baner på grund af de begrænsede kolonnebalancer.
Vi når derfor et tidspunkt, hvor alle fem baner er permanent besat og fast knyttet til en formular. Fra dette tidspunkt tæller vi \(t\) flere sten og med \(n_j(t)\) tallet i spor \(j\) . Hver af disse sten bidrager med to celler til hver kolonne af dens spor. Fordi rækkesletninger behandler alle kolonner ens, forbliver forskellene \(n_j(t)-n_k(t)\) begrænsede. På længere sigt skal alle fem baner hver rumme en femtedel af stenene:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Hvis \(k\) af de fem baner er reserveret til S-sten, bør deres andel være omkring \(k/5\) . Men i den skiftende rækkefølge er det \(1/2\) : i hvert præfiks er numrene på S- og Z-stenene højst forskellige med \(1\) . Opdelingen af banerne skulle opfylde begge dele på samme tid. En andel på halvdelen kan dog ikke repræsenteres som summen af hele femtedele. Det er her frekvensen af vekslende former og det ulige antal af lige brugte spor mødes. Det ville være obligatorisk:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Antallet af baner er et heltal. Denne modsigelse afslutter antagelsen om et uendeligt spil. Argumentet viser også, hvorfor tavlebredden er en del af det: Med fire tog ville en opdeling i to S- og to Z-tog ikke være udelukket af denne modsætning. Til det tilfældige bevis har vi brug for en endelig bloklængde \(N\) , der fører til tab uanset det aktuelle bord. "Hver strategi taber på et tidspunkt" alene er ikke nok.
Ensartetheden følger af det endelige antal mulige tilstande. Efter hver afsluttet placering er der højst \(2^{200}\) belægningsmønstre. Der er også information om, hvorvidt S eller Z vises næste, dvs. maksimalt \(2^{201}\) tilstande. Hvis du skulle overleve \(N=2^{201}\) sten, ville \(N+1\) -tilstandene før og efter disse træk have en gentagelse. På grund af det identiske bræt og den samme næste form, ville de lovlige træk derimellem kunne gentages et vilkårligt antal gange: det uendelige spil er lige udelukket.
Grænsen tæller også uopnåelige brætmønstre og forudsiger ikke praktisk spillængde. Burgiels finere geometriske tælling giver mindre grænser; her er en endelig \(N\) tilstrækkelig. Det gælder for alle tilladte indledende tildelinger og begge faser af S/Z-sekvensen. Lad os dekomponere den uendelige tilfældige sekvens i usammenhængende blokke med længden \(N\) . Hver blok er nøjagtig den specificerede sekvens \(S,Z,S,Z,\ldots\) med sandsynlighed \(q=7^{-N}>0\) . Blokkene er uafhængige. Det er derfor sandsynligt, at ingen af de første \(m\) blokke indeholder denne sekvens:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Så med sandsynlighed \(1\) vil en dødelig blok dukke op på et tidspunkt, medmindre spillet slutter inden da. Dette gælder også med enhver tid til at tænke over det og fuldstændig viden om hele rækkefølgen af sten. Dette resulterer ikke i kort praktisk spilletid. En ufokuseret, dårlig start alene betyder ikke nederlag; overraskende comebacks er bestemt mulige. Så – bliv ikke modløs og nyd det tidløse spil.