Оптималдуу ойнобогонуңуздан же ката кетиргениңизден улам Тетристе утулуп жатасызбы? Ал тургай, бул жөнүндө ойлонуп, бир жагымсыз ырааттуу таштарды сактап калуу мүмкүн эмес. Чечүүчү фактор - беш тар тилке жана так сан. Биз \(10\) мамычалар жана \(20\) саптары менен алмашуу буфери жок оюн талаасын карап чыгабыз (кармап туруу): Ар бир жаңы таш өз алдынча тартылып, жети тетроминодон бирдей бөлүштүрүлөт. Ар бир фигура бириктирилген төрт чарчыдан турат. Бардык эпизод алдын ала белгилүү болушу мүмкүн.
Оюндун дээрлик сөзсүз бүтүшү мүмкүн болгон таштардын ар бир ырааттуулугу бүтөт дегенди билдирбейт. O-таштарынын таза ырааттуулугун чексиз ойносо болот: бири-бирине жанаша жайгашкан беш квадрат эки катарды жок кылып, тактаны бошотот. 7-Багда ар бир туш келди аралаштырылган баштыкта бардык жети фигураны бир жолу камтыйт; биздин кокустук аргумент буга тиешеси жок. Тетристе кантип утулса болот, Хайди Бургиэл идеалдуу оюн да жардам бербеген ырааттуулукту көрсөтөт: \(S,Z,S,Z,\ldots\) .
S жана Z бир эле таштын ар кандай айлануусу эмес, күзгү сүрөттөрү. Коштоочу түшүндүрмө биз бул жерде карама-каршылык менен далил катары келтирген геометриялык идеяны сүрөттөйт. "Кээ бир учурда Z таштары гана пайда болот жана алар менен бирге эч бир катар жок болбойт" деген ачык-айкын пикир туура эмес. Болгону беш окшош, вертикалдуу жайгаштырылган S-таштары башында бош болгон тактада төмөнкүдөй тартипти камсыз кылат. Ошол эле тамгалар ошол эле ташты көрсөтүп турат; Чекиттер бош орундарды белгилейт:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eОртоңку катар толукталып, өчүрүлдү. Эгер аранжировканы чагылдырсаңыз, Z-таштары үчүн ошол эле каршы мисалды аласыз. Маселе жеке саптарды жок кылууда эмес, чексиз сандагы таштарда пайда болгон бардык дисбаланстарды көзөмөлдөй аласызбы деген суроо. \(1\) дан \(10\) чейин мамычаларды номерлейли. \(b_i\) менен \(i\) графасына жайгаштырылган бардык жаңы уячалардын жалпы санын, анын ичинде кийинчерээк өчүрүлгөндөрдү белгилейбиз.
\(h_i\) \(i\) жана \(i+1\) мамычаларындагы ортоңку мамыча \(i\) , \(v_i\) тик таштары бар горизонталдуу S же Z таштарды санайт. Эсептегичтер учурда көрүнгөн стекти эле эмес, оюндун жүрүшүн жазат. Горизонталдык таш өзүнүн клеткаларын \(1,2,1\) катышта үч мамычага, вертикалдуу таш \(2,2\) катышы боюнча эки мамычага бөлүштүрөт. Эки күзгү сүрөттөр бирдей мамычанын балансына ээ. Эгер сиз бул салымдарды бардык жайгаштыруулар боюнча кошсоңуз, ар бир тилке үчүн аласыз:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Тактанын сыртында биз бардык эсептегичтерди \(0\) деп койдук; атап айтканда \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Бул чек ара конвенциясы тең салмактуулукту оюн талаасынын четинен чыгып кете турган таштарды эсептөөгө жол бербейт. Биздин моделде мындай жайгаштырууга жол берилбейт. Эгерде каралып жаткан S/Z ырааттуулугу толтурулган тактадан башталса, \(a_i\) башында ээлеген уячалар жана \(c_i\) \(i\) тилкесинде учурда ээлеген уячалар болсун. \(R\) жок кылынган саптардан кийин:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Оюн иштеп жаткан учурда, бардык \(a_i,c_i\) \(0\) менен \(20\) ортосунда болот. Ошондуктан \(|b_i-b_j|\leq40\) колдонулат. Эгер такта башында бош болсо \(20\) жетиштүү. Ар бир жок кылынган сап ар бир тилкеден бир уячаны алып салат. Мына ошондуктан, эки мамычаны салыштырганда өчүрүлгөн саптардын саны азаят, ал тургай, коюлган уячалардын эсептегичтери өсө берсе дагы. Стек бийиктиктеринин ордуна ээлеген клеткаларды санайсыз; Тешиктерге келгенде эки өлчөм айырмаланат. Бул чекти жалпысынан \(D\) деп жазсак, ал сол же оң жээкке чыгат:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Ички мамыча жуптары үчүн эки чектелген мамыча айырмасын кошобуз: \(b_4-b_3\) жана \(b_2-b_1\) сол жакта, \(b_7-b_8\) жана \(b_9-b_{10}\) оң. Мамыча балансын киргизгенден кийин, ортосундагы эсептегичтер бири-бирин так жокко чыгарышат. Бул ар бир сол тарапта \(2D\) менен бирге чектелген терс эмес салымдарды гана калтырат. Бул бизге эки ички жуп үчүн тиешелүү жайгаштыруу номерлери үчүн жогорку чекти берет:
$$\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}$$
Эгерде төрт теңсиздикти кошсок, ар бир горизонталдуу таш так бир жолу эсептелет. Кайчылаш тик тик жайгаштыруунун төрт түрү да оң коэффициенттерге ээ. Горизонталдуу таштар үч мамычаны ээлейт, ошондуктан кийинчерээк каралып жаткан эки мамычалуу жолдордун бирине толук туура келбейт. Тик таштар үчүн биз сол мамычага ылайык тректерди айырмалайбыз. Бардык эсептегичтер терс эмес болгондуктан, бул салымдардын бири дагы башка тарабынан жокко чыгарыла албайт:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Түз сол мамыча менен горизонталдуу жайгаштыруу жана вертикалдуу жайгаштыруу бош тактада максимум \(120\) жолу же алдын ала толтурулган ар кандай тактада \(240\) жолу болушу мүмкүн. Бул иш жүзүндө жетишүүгө болот деген доомат эмес, жогорку чек болуп саналат. Кандай болбосун, бул качуу кыймылдарын чексиз көп колдонуу мүмкүн эмес. Эми сиз кезектеги ырааттуулукту чексиз ойной аласыз деп ойлойлу.
Чектүү сандагы качуу кыймылдарынан кийин, беш туруктуу тилкеге вертикалдуу жайгаштыруу гана мүмкүн болмок: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Окшош формалар бири-бирине тепкич сымал формада туура келет: түбү мурунку таштын дал чокусуна туура келет. Sдан Яга же тескерисинче өзгөртүү бир клетканын туурасы жана эки клетканын тереңдигинен боштук калтырат. Деталь S-таштын үстүнөн Z-ташын көрсөтөт; экөө тең "o" ажырымды белгилейт:
.Z
ZZ
Zo
So
SS
.SОшол эле тилкедеги дагы бир вертикалдуу таш бул боштукту толтура албайт: анын экинчи тилкеси кошуна ээлеген клеткалар менен кагылышат. Катарларды жок кылуу боштук ачык болсо да жардам бербейт, анткени эки сап тең толук эмес. Оңдоо мурунтан эле алынып салынган кайчылаш трассанын же горизонталдуу жайгаштыруунун бирин талап кылат. Акыркы качуудан кийин мындай боштуктар туруктуу болуп калат. Чектүү тактада чексиз сандагы жаңы, ажыратылган боштуктар пайда болушу мүмкүн эмес.
Натыйжада, тректердеги формада чектүү сандагы өзгөртүүлөр гана болушу мүмкүн. Башында бош тилке муну өзгөртпөйт: сиздин биринчи S же Z ташыңыз полдо бир мамычалуу боштук калтырат, аны андан ары таза тилке ойнотуу менен жабууга болбойт. Чексиз делген оюнда ар бир тилкеде чексиз таштар да болушу керек. Эгерде тилке кандайдыр бир учурда тийбей кала турган болсо, мамычанын баланстары чектелгендиктен, калган тилкелерге чектүү сандагы уячалар гана жайгаштырылышы мүмкүн.
Ошентип, биз бардык беш тилке биротоло ээленип, формага бекем орнотулган убакытка жеттик. Ушул учурдан баштап биз \(t\) дагы таштарды жана \(n_j(t)\) менен \(j\) жолундагы санды санайбыз. Бул таштардын ар бири өз жолунун ар бир мамычасына экиден клетканы түзөт. Саптарды жок кылуу бардык мамычаларды бирдей карагандыктан, \(n_j(t)-n_k(t)\) айырмачылыктар чектелүү бойдон калууда. Узак мөөнөттүү келечекте бардык беш тилкеде таштардын бештен бир бөлүгү болушу керек:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Беш тилкенин \(k\) S-таштары үчүн сакталган болсо, алардын үлүшү \(k/5\) тегерегинде болушу керек. Бирок, кезектешип кезекте ал \(1/2\) болот: ар бир префиксте S жана Z таштарынын саны эң көп \(1\) менен айырмаланат. Жолдордун бөлүнүшү бир эле учурда эки бөлүктүн тең аткарылышы керек болчу. Бирок, жарым үлүшүн толук бештен суммасы катары көрсөтүү мүмкүн эмес. Бул жерде алмашып туруучу формалардын жыштыгы жана бирдей колдонулган тректердин так саны биригет. Бул милдеттүү болмок:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Жолдордун саны бүтүн сан. Бул карама-каршылык чексиз оюндун божомолун аяктайт. Аргумент ошондой эле тактанын туурасы эмне үчүн анын бир бөлүгү экенин көрсөтүп турат: Төрт поезд менен эки S жана эки Z поездине бөлүнүүнү бул карама-каршылык жокко чыгарбайт. Кокус далилдөө үчүн бизге учурдагы тактага карабастан жоготууга алып келген чектүү блок узундугу \(N\) керек. "Ар бир стратегия качандыр бир убакта утулуп калат" деген гана жетиштүү эмес.
Бир тектүүлүк мүмкүн болгон абалдардын чектүү санынан келип чыгат. Ар бир аяктагандан кийин, эң көп дегенде \(2^{200}\) ээлөө үлгүлөрү болот. Андан кийин S же Z пайда болобу, б.а. максимум \(2^{201}\) абалына байланыштуу маалымат бар. Эгер сиз \(N=2^{201}\) таштардан аман калсаңыз, бул кыймылдарга чейинки жана кийинки \(N+1\) абалдары кайталанат. Окшош такта жана ошол эле кийинки форма болгондуктан, алардын ортосундагы мыйзамдуу кыймылдар каалаган санда кайталана берет: чексиз оюн жөн эле алынып салынган.
Чек ошондой эле кол жеткис такта үлгүлөрүн эсептейт жана практикалык оюндун узактыгын алдын ала бербейт. Бургиелдин геометриялык геометриялык саноо азыраак чектерди берет; бул жерде чектүү \(N\) жетиштүү. Ал бардык уруксат берилген баштапкы тапшырмаларга жана S/Z ырааттуулугунун эки фазасына тиешелүү. Чексиз кокус ырааттуулукту \(N\) узундуктагы бөлүнүүчү блокторго бөлөлү. Ар бир блок так көрсөтүлгөн ырааттуулук \(S,Z,S,Z,\ldots\) ыктымалдыгы \(q=7^{-N}>0\) . блоктор көз карандысыз болуп саналат. Демек, биринчи \(m\) блоктордун бири да бул ырааттуулукту камтыбайт:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Ошентип \(1\) ыктымалдыгы менен, эгер оюн ага чейин бүтпөсө, кандайдыр бир учурда өлүмгө дуушар болгон блок пайда болот. Бул ошондой эле ал жөнүндө ойлонууга жана таштардын бүт ырааттуулугун толук билүү үчүн каалаган убакытка тиешелүү. Бул кыска практикалык ойноо убактысына алып келбейт. Жалгыз көңүл бурулбаган, жаман башталышы жеңилүүнү билдирбейт; таң калыштуу кайтуулар, албетте, мүмкүн. Андыктан - көңүлүңүздү чөгөрбөңүз жана түбөлүктүү оюндан ырахат алыңыз.