Humbni në Tetris vetëm sepse nuk luani në mënyrë optimale apo bëni gabime? Edhe me çdo kohë për të menduar për të, një sekuencë e pafavorshme gurësh nuk mund të shpëtohet. Faktori vendimtar janë pesë korsi të ngushta dhe një numër tek. Ne konsiderojmë një fushë loje me \(10\) kolona dhe \(20\) rreshta pa një tastierë (mbaj): Çdo gur i ri vizatohet në mënyrë të pavarur dhe shpërndahet në mënyrë të barabartë nga shtatë tetrominoet . Çdo formë përbëhet nga katër katrorë të lidhur. I gjithë episodi mund të dihet paraprakisht.
Fakti që një lojë pothuajse me siguri përfundon nuk do të thotë se çdo sekuencë e mundshme gurësh përfundon. Një sekuencë e pastër e gurëve O mund të luhet pafundësisht: pesë katrorë të vendosur pranë njëri-tjetrit fshijnë dy rreshta dhe zbrazin tabelën. Në 7-Bag, çdo qese e përzier rastësisht përmban të shtatë format saktësisht një herë; argumenti ynë i rastësisë nuk vlen për këtë. Në Si të humbasësh në Tetris, Heidi Burgiel tregon një sekuencë që edhe loja e përsosur nuk ndihmon: \(S,Z,S,Z,\ldots\) .
S dhe Z janë imazhe pasqyre, jo rrotullime të ndryshme të të njëjtit gur. Shpjegimi shoqërues përshkruan idenë gjeometrike që ne paraqesim këtu si një provë me kontradiktë. Pretendimi i qartë "në një moment shfaqen vetëm gurët Z dhe asnjë rresht nuk zhduket me ta" është i gabuar. Vetëm pesë gurë S identikë, të vendosur vertikalisht, ofrojnë rregullimin e mëposhtëm në një tabelë fillimisht të zbrazët. Të njëjtat shkronja tregojnë të njëjtin gur; Pikat shënojnë hapësirat e lira:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eRreshti i mesëm është i plotë dhe i fshirë. Nëse pasqyroni rregullimin, merrni të njëjtin kundërshembull për gurët Z. Problemi nuk është fshirja e rreshtave individualë, por pyetja nëse mund të kontrolloni të gjitha çekuilibrat që lindin në një numër të pakufizuar gurësh. Le të numërojmë kolonat nga \(1\) në \(10\) . Me \(b_i\) shënojmë numrin total të të gjitha qelizave të reja të vendosura në kolonën \(i\) , duke përfshirë ato të fshira më vonë.
\(h_i\) numëron gurët horizontalë S ose Z me kolonën e mesme \(i\) , \(v_i\) gurët vertikalë në kolonat \(i\) dhe \(i+1\) . Numëruesit regjistrojnë rrjedhën e lojës, jo vetëm grumbullin e dukshëm aktualisht. Një gur horizontal i shpërndan qelizat e tij në raportin \(1,2,1\) mbi tre kolona, një gur vertikal në raportin \(2,2\) në dy kolona. Të dy imazhet e pasqyrës kanë të njëjtin ekuilibër të kolonës. Nëse i shtoni këto kontribute në të gjitha vendosjet, ju merrni për secilën kolonë:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Jashtë tabelës i vendosim të gjithë numëruesit në \(0\) ; në veçanti \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Kjo konventë e skajeve parandalon balancën nga numërimi i gurëve që do të shtriheshin përtej skajit të fushës së lojës. Vendosje të tilla nuk lejohen në modelin tonë. Nëse sekuenca S/Z në shqyrtim fillon në një tabelë tashmë të mbushur, le të jenë \(a_i\) qelizat e zëna fillimisht dhe \(c_i\) qelizat e zëna aktualisht në kolonën \(i\) . Pas \(R\) rreshtave të fshirë është:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Për sa kohë që loja është duke u ekzekutuar, të gjitha \(a_i,c_i\) janë midis \(0\) dhe \(20\) . Prandaj \(|b_i-b_j|\leq40\) vlen. Nëse bordi fillimisht është bosh \(20\) mjafton. Çdo rresht i fshirë heq saktësisht një qelizë nga secila kolonë. Kjo është arsyeja pse numri i rreshtave të fshirë zvogëlohet kur krahasohen dy kolona, edhe nëse numëruesit e qelizave të vendosura vazhdojnë të rriten. Ju numëroni qelizat e zëna në vend të lartësive të stivit; Dy madhësitë ndryshojnë kur bëhet fjalë për vrimat. Nëse e shkruajmë këtë kufi në përgjithësi si \(D\) , ai rezulton në skajin e majtë ose të djathtë:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Për çiftet e kolonave të brendshme shtojmë dy dallime të kufizuara të kolonave: \(b_4-b_3\) dhe \(b_2-b_1\) në të majtë, \(b_7-b_8\) dhe \(b_9-b_{10}\) në të djathtë. Pas futjes së bilancit të kolonës, numëruesit në mes anulojnë saktësisht njëri-tjetrin. Kjo lë vetëm kontribute jo negative në secilën anë të majtë, të cilat kufizohen bashkërisht nga \(2D\) . Kjo na jep gjithashtu një kufi të sipërm për numrat përkatës të vendosjes për dy çiftet e brendshme:
$$\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}$$
Nëse shtojmë katër pabarazitë, çdo gur horizontal numërohet saktësisht një herë. Katër llojet e vendosjeve vertikale të kryqëzuara kanë gjithashtu koeficientë pozitivë. Gurët horizontale zënë tre kolona dhe për këtë arsye nuk përshtaten plotësisht në një nga shtigjet me dy kolona të konsideruara më vonë. Për gurët vertikal dallojmë gjurmët sipas kolonës së majtë. Meqenëse të gjithë numëruesit janë jonegativë, asnjë nga këto kontribute nuk mund të anulohet nga një tjetër:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Prandaj, vendosjet horizontale dhe vendosjet vertikale me një kolonë të drejtë majtas mund të ndodhin maksimumi \(120\) herë në një tabelë bosh ose \(240\) herë në çdo tabelë të mbushur paraprakisht. Ky është një kufi i sipërm, jo një pretendim se ai në të vërtetë mund të arrihet. Në çdo rast, këto lëvizje evazive nuk mund të përdoren pafundësisht shpesh. Tani le të supozojmë se mund të luani sekuencën alternative për një kohë të pacaktuar.
Pas fundit të numrit të kufizuar të lëvizjeve evazive, do të ishin të mundshme vetëm vendosjet vertikale në pesë korsi fikse: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Format identike përshtaten me njëra-tjetrën në një model të ngjashëm me hapin: pjesa e poshtme takon majën e përputhshme të gurit të mëparshëm. Ndryshimi nga S në Z ose anasjelltas lë një boshllëk një qelizë të gjerë dhe dy qeliza të thella. Detaji tregon një gur Z mbi një gur S; të dyja "o" shënojnë boshllëkun:
.Z
ZZ
Zo
So
SS
.SNjë gur tjetër vertikal në të njëjtën korsi nuk mund ta mbushë këtë boshllëk: kolona e tij e dytë do të përplasej me qelitë e pushtuara fqinje. Fshirja e rreshtave nuk ndihmon as për sa kohë që hendeku është i hapur, sepse të dy rreshtat nuk janë të plotë. Një riparim kërkon një nga vendosjet tashmë të përjashtuara të tërthorta ose horizontale. Pas lëvizjes së fundit evazive, boshllëqe të tilla janë të përhershme. Një numër i pafund boshllëqesh të reja, të shkëputura nuk mund të lindin në një tabelë të fundme.
Si rezultat, mund të ketë vetëm një numër të kufizuar ndryshimesh në formë në pista. Një korsi fillimisht e zbrazët nuk e ndryshon këtë: guri juaj i parë S ose Z tashmë lë një boshllëk me një kolonë në dysheme që nuk mund të mbyllet me lojë të mëtejshme të pastër korsie. Në një lojë të supozuar të pafund, çdo korsi duhet të mbajë gjithashtu një numër të pafund gurësh. Nëse një korsi do të mbetej e paprekur në një moment, vetëm një numër i kufizuar qelizash mund të vendoseshin në korsitë e mbetura për shkak të balancave të kufizuara të kolonës.
Prandaj arrijmë në një pikë kohore në të cilën të pesë korsitë janë të zëna përgjithmonë dhe të caktuar fort në një formular. Nga kjo pikë e tutje ne numërojmë \(t\) më shumë gurë dhe me \(n_j(t)\) numrin në pistën \(j\) . Secili prej këtyre gurëve kontribuon me dy qeliza në secilën kolonë të gjurmës së tij. Për shkak se fshirjet e rreshtave i trajtojnë të gjitha kolonat në mënyrë të barabartë, dallimet \(n_j(t)-n_k(t)\) mbeten të kufizuara. Në terma afatgjatë, të pesë korsitë duhet të mbajnë secila një të pestën e gurëve:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Nëse \(k\) nga pesë korsitë janë të rezervuara për gurët S, pjesa e tyre duhet të jetë rreth \(k/5\) . Megjithatë, në sekuencën alternative është \(1/2\) : në çdo parashtesë numrat e gurëve S dhe Z ndryshojnë me maksimum \(1\) . Ndarja e korsive do të duhej të përmbushte të dyja pjesët në të njëjtën kohë. Megjithatë, një pjesë prej gjysmë nuk mund të përfaqësohet si shuma e të pestave të plota. Këtu bashkohen frekuenca e formave të alternuara dhe numri tek i gjurmëve të përdorura njësoj. Kjo do të ishte e detyrueshme:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Numri i korsive është një numër i plotë. Kjo kontradiktë i jep fund supozimit të një loje të pafundme. Argumenti tregon gjithashtu pse gjerësia e tabelës është pjesë e saj: Me katër trena, një ndarje në dy trena S dhe dy Z nuk do të përjashtohej nga kjo kontradiktë. Për vërtetimin e rastësishëm na nevojitet një gjatësi blloku të fundëm \(N\) që çon në humbje pavarësisht nga bordi aktual. "Çdo strategji humbet në një moment" vetëm nuk mjafton.
Uniformiteti rrjedh nga numri i kufizuar i gjendjeve të mundshme. Pas çdo vendosjeje të përfunduar, ka maksimumi \(2^{200}\) modele zënie. Ekziston gjithashtu informacioni nëse S ose Z shfaqet më pas, pra një maksimum prej gjendjeve \(2^{201}\) . Nëse do t'u mbijetoje gurëve \(N=2^{201}\) , gjendjet \(N+1\) para dhe pas këtyre lëvizjeve do të kenë një përsëritje. Për shkak të tabelës identike dhe të njëjtës formë tjetër, lëvizjet ligjore në mes do të ishin të përsëritshme çdo herë: loja e pafundme sapo përjashtohej.
Kufiri gjithashtu numëron modelet e paarritshme të tabelës dhe nuk parashikon gjatësinë praktike të lojës. Numërimi më i imët gjeometrik i Burgiel jep kufij më të vegjël; këtu mjafton një \(N\) e fundme. Ai zbatohet për të gjitha caktimet fillestare të lejuara dhe të dy fazat e sekuencës S/Z. Le të zbërthejmë sekuencën e rastësishme të pafundme në blloqe të shkëputura të gjatësisë \(N\) . Çdo bllok është saktësisht sekuenca e specifikuar \(S,Z,S,Z,\ldots\) me probabilitet \(q=7^{-N}>0\) . Blloqet janë të pavarura. Prandaj është e mundur që asnjë nga blloqet e para \(m\) të mos e përmbajë këtë sekuencë:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Pra, me probabilitet \(1\) një bllok vdekjeprurës do të shfaqet në një moment, përveç nëse loja përfundon para kësaj. Kjo vlen edhe për çdo kohë për të menduar për të dhe njohuri të plotë të të gjithë sekuencës së gurëve. Kjo nuk rezulton në një kohë të shkurtër loje praktike. Vetëm një fillim i papërqëndruar, i keq nuk do të thotë humbje; Rikthimet befasuese janë sigurisht të mundshme. Pra - mos u dekurajoni dhe shijoni lojën e përjetshme.