Apa sampeyan mung kalah ing Tetris amarga sampeyan ora main kanthi optimal utawa nggawe kesalahan? Sanajan sawetara wektu kanggo mikir babagan iki, urutan watu sing ora apik ora bisa disimpen. Faktor sing nemtokake yaiku limang jalur sing sempit lan nomer ganjil. We nimbang lapangan playing karo \(10\) kolom lan \(20\) larik tanpa clipboard (ditahan): Saben watu anyar digambar independen lan merata mbagekke saka pitu tetrominoes . Saben wangun kasusun saka papat kothak nyambung. Kabeh episode bisa dingerteni sadurunge.
Kasunyatan bilih game meh mesthi ends ora ateges sing saben urutan kepikiran saka watu ends. A urutan murni saka O-watu bisa diputer endlessly: limang kothak diselehake ing jejere saben liyane mbusak loro larik lan kosongaké Papan. Ing 7-Bag, saben tas campuran acak ngemot kabeh pitung wangun persis sapisan; argumentasi kasempatan kita ora ditrapake kanggo iki. Ing Carane Kalah ing Tetris, Heidi Burgiel nuduhake urutan sing malah sampurna muter ora mbantu: \(S,Z,S,Z,\ldots\) .
S lan Z minangka gambar pangilon, ora beda rotasi saka watu sing padha. Panjelasan ing ngisor iki nggambarake ide geometris sing disedhiyakake ing kene minangka bukti kanthi kontradiksi. Klaim sing jelas "ing sawetara titik mung watu Z sing katon lan ora ana baris sing ilang" salah. Mung limang podho rupo, vertikal diselehake S-watu nyedhiyani noto ing ngisor iki ing Papan pisanan kosong. Huruf sing padha nuduhake watu sing padha; Titik menehi tandha spasi kosong:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eBaris tengah wis rampung lan dibusak. Yen kaca noto, sampeyan njaluk counterexample padha Z-watu. Masalah ora mbusak larik individu, nanging pitakonan apa sampeyan bisa ngontrol kabeh imbalances sing njedhul tengen nomer Unlimited watu. Wilangan kolom saka \(1\) nganti \(10\) . Miturut \(b_i\) kita nuduhake jumlah total kabeh sel anyar sing diselehake ing kolom \(i\) , kalebu sing dibusak mengko.
\(h_i\) ngetung watu S utawa Z horisontal kanthi kolom tengah \(i\) , \(v_i\) watu vertikal ing kolom \(i\) lan \(i+1\) . Counter ngrekam dalan game, ora mung tumpukan saiki sing katon. Watu horisontal nyebarake sel ing rasio \(1,2,1\) liwat telung kolom, watu vertikal ing rasio \(2,2\) ing rong kolom. Loro gambar pangilon duwe imbangan kolom sing padha. Yen sampeyan nambahake kontribusi kasebut ing kabeh penempatan, sampeyan entuk saben kolom:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Njaba Papan kita nyetel kabeh counters kanggo \(0\) ; khususe \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Konvènsi pinggiran iki ngalangi imbangan saka watu ngetang sing bakal ngluwihi pinggiran lapangan playing. Penempatan kasebut ora diidini ing model kita. Yen urutan S/Z sing dipikirake diwiwiti ing papan sing wis diisi, mula \(a_i\) dadi sel sing dikuwasani lan \(c_i\) sel sing saiki dikuwasani ing kolom \(i\) . Sawise \(R\) dibusak baris punika:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Anggere game mlaku, kabeh \(a_i,c_i\) antarane \(0\) lan \(20\) . Mulane \(|b_i-b_j|\leq40\) ditrapake. Yen papan wiwitane kosong \(20\) cukup. Saben baris dibusak njupuk persis siji sel saka saben kolom. Iki kok jumlah larik dibusak wis suda nalika mbandhingaké rong kolom, malah yen counters saka sel nyetel terus kanggo tuwuh. Sampeyan ngetung sel sing dikuwasani tinimbang dhuwur tumpukan; Loro ukuran beda-beda nalika nerangake bolongan. Yen kita nulis watesan iki umume minangka \(D\) , asil ing pinggir kiwa utawa tengen:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Kanggo pasangan kolom njero kita nambahake rong beda kolom sing diwatesi: \(b_4-b_3\) lan \(b_2-b_1\) ing sisih kiwa, \(b_7-b_8\) lan \(b_9-b_{10}\) ing sisih tengen. Sawise nglebokake imbangan kolom, counters ing antarane mbatalake saben liyane metu persis. Iki mung ninggalake kontribusi non-negatif ing saben sisih kiwa, sing diwatesi bebarengan karo \(2D\) . Iki uga menehi kita watesan ndhuwur kanggo nomer panggonan seko pamilike kanggo loro pasangan utama:
$$\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}$$
Yen kita nambah papat inequalities, saben watu horisontal diitung persis sapisan. Papat jinis penempatan vertikal lintas-trek uga nduweni koefisien positif. Watu horisontal njupuk telung kolom lan mulane ora pas karo salah sawijining jalur rong kolom sing dianggep mengko. Kanggo watu vertikal, kita mbedakake trek miturut kolom kiwa. Amarga kabeh counter non-negatif, ora ana kontribusi iki bisa dibatalake dening liyane:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Penempatan horisontal lan penempatan vertikal kanthi kolom kiwa lurus bisa kedadeyan maksimal kaping \(120\) ing papan kosong utawa kaping \(240\) ing papan sing wis diisi. Iki minangka wates ndhuwur, dudu pratelan manawa bisa ditindakake. Ing kasus apa wae, gerakan evasive iki ora bisa digunakake kanthi asring. Saiki ayo nganggep sampeyan bisa muter urutan gantian tanpa wates.
Sawise pungkasan saka jumlah winates saka gerakan evasive, mung panggonan vertikal ing limang dalan tetep bakal bisa: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Wangun sing padha pas karo saben liyane ing pola langkah-langkah: sisih ngisor ketemu ndhuwur sing cocog karo watu sadurunge. Ngganti saka S dadi Z utawa kosok balene ninggalake celah siji sel amba lan rong sel jero. Rincian nuduhake Z-watu liwat S-watu; loro "o" tandha longkangan:
.Z
ZZ
Zo
So
SS
.SWatu vertikal liyane ing jalur sing padha ora bisa ngisi celah iki: kolom kapindho bakal tabrakan karo sel sing dikuwasani tetanggan. Mbusak baris ora bisa mbantu anggere longkangan mbukak, amarga loro baris ora lengkap. A ndandani mbutuhake salah siji saka wis tilar lintas-trek utawa placements horisontal. Sawise pamindhahan evasive pungkasan, kesenjangan kuwi permanen. Nomer tanpa wates anyar, kesenjangan disjoint ora bisa muncul ing papan sing winates.
Akibaté, mung bisa ana sawetara owah-owahan ing wangun ing trek. Lane kosong pisanan ora ngganti iki: watu S utawa Z pisanan sampeyan wis ninggalake longkangan siji-kolom ing lantai sing ora bisa ditutup dening play lane luwih murni. Ing game sing mesthine tanpa wates, saben jalur uga kudu ngemot watu tanpa wates. Yen jalur tetep ora kena ing sawetara titik, mung sawetara sel sing bisa ditampung ing jalur sing isih ana amarga imbangan kolom sing winates.
Mulane kita tekan titik ing wektu ing ngendi kabeh limang jalur dikuwasani kanthi permanen lan ditugasake kanthi kuat menyang formulir. Saka titik iki kita count \(t\) watu liyane lan karo \(n_j(t)\) nomer ing trek \(j\) . Saben watu iki nyumbang rong sel kanggo saben kolom trek. Amarga pambusakan baris nganggep kabeh kolom kanthi padha, bedane \(n_j(t)-n_k(t)\) tetep diwatesi. Ing jangka panjang, kabeh limang jalur kasebut kudu ngemot seperlima watu:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Yen \(k\) saka limang jalur dicadhangake kanggo watu-S, bagean kasebut kudu watara \(k/5\) . Nanging, ing urutan gantian iku \(1/2\) : ing saben ater-ater nomer watu S lan Z beda paling \(1\) . Pembagian jalur kasebut kudu ngrampungake loro bagean kasebut bebarengan. Nanging, bagean saka setengah ora bisa diwakili minangka gunggunge kabeh seperlima. Iki ngendi frekuensi gantian formulir lan nomer ganjil trek merata digunakake bebarengan. Sing bakal dadi wajib:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Jumlah lajur minangka integer. Kontradiksi iki mungkasi asumsi saka game tanpa wates. Argumentasi uga nuduhake apa jembaré Papan minangka bagéan saka iku: Kanthi papat sepur, divisi dadi loro S lan loro Z sepur ora bakal dikalahake dening kontradiksi iki. Kanggo bukti acak kita kudu dawa pemblokiran winates \(N\) sing ndadékaké kanggo mundhut preduli saka Papan saiki. "Saben strategi ilang ing sawetara titik" piyambak ora cukup.
Keseragaman kasebut dumadi saka jumlah negara sing bisa ditemtokake. Sawise saben penempatan rampung, paling akeh \(2^{200}\) pola pendhudhukan. Ana uga informasi apa S utawa Z katon sabanjure, yaiku maksimal \(2^{201}\) negara. Yen sampeyan kudu slamet ing watu \(N=2^{201}\) , \(N+1\) nyatakake sadurunge lan sawise gerakan kasebut bakal duwe pengulangan. Amarga saka Papan podho rupo lan wangun sabanjuré padha, gerakane legal ing antarane bakal repeatable sawetara kaping: game tanpa wates mung tilar.
Watesan uga ngetung pola papan sing ora bisa ditindakake lan ora prédhiksi dawa game praktis. pancacahan geometris nggoleki Burgiel menehi wates cilik; kene winates \(N\) cukup. Iki ditrapake kanggo kabeh tugas awal sing diidinake lan loro fase urutan S / Z. Ayo kita decompose urutan acak tanpa wates menyang pamblokiran disjoint dawa \(N\) . Saben blok persis urutan sing ditemtokake \(S,Z,S,Z,\ldots\) kanthi probabilitas \(q=7^{-N}>0\) . Blok kasebut independen. Mulane, kemungkinan ora ana blok \(m\) pisanan sing ngemot urutan iki:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Dadi karo kemungkinan \(1\) pemblokiran agawe bakal katon ing sawetara titik, kajaba game ends sadurunge banjur. Iki uga ditrapake kanggo wektu apa wae kanggo mikir babagan lan kawruh lengkap babagan akibat. Iki ora kasil ing wektu game praktis singkat, lan wiwitan ala piyambak ora ateges asor: Animasi ing ngisor iki nuduhake limang urutan campuran wis diwilang, saben kang tekan Papan kosong sawise sangang placements menara panggah. Dheweke dudu bot Tetris universal.