Դուք պարտվում եք միայն Tetris-ում այն պատճառով, որ օպտիմալ չե՞ք խաղում կամ սխալվում եք: Նույնիսկ դրա մասին մտածելու ցանկացած ժամանակի դեպքում, քարերի անբարենպաստ հաջորդականությունը հնարավոր չէ փրկել: Որոշիչ գործոնը հինգ նեղ գծերն են և կենտ թիվը: Մենք հաշվի ենք առնում խաղադաշտը \(10\) սյունակներով և \(20\) տողերով առանց clipboard (պահում). Յուրաքանչյուր նոր քար գծվում է ինքնուրույն և հավասարապես բաշխվում է յոթ տետրոմինոներից : Յուրաքանչյուր ձև բաղկացած է չորս միացված քառակուսիներից: Ամբողջ դրվագը հնարավոր է նախապես հայտնի լինի։
Այն փաստը, որ խաղը գրեթե անկասկած ավարտվում է, չի նշանակում, որ քարերի ամեն հնարավոր հաջորդականություն ավարտվում է: O-քարերի մաքուր հաջորդականությունը կարելի է անվերջ խաղալ. իրար կողքի դրված հինգ քառակուսիները ջնջում են երկու տող և դատարկում տախտակը: 7-Bag-ում յուրաքանչյուր պատահականորեն խառնված պարկը պարունակում է բոլոր յոթ ձևերը ուղիղ մեկ անգամ. մեր պատահական փաստարկը սրան չի վերաբերում: Ինչպես կորցնել Tetris-ում, Հայդի Բուրգիելը ցույց է տալիս մի հաջորդականություն, որին նույնիսկ կատարյալ խաղը չի օգնում \(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\) հաշվում է հորիզոնական S կամ Z քարերը միջին սյունակով \(i\) , \(v_i\) ուղղահայաց քարերով \(i\) և \(i+1\) սյունակներում: Հաշվիչները գրանցում են խաղի ընթացքը, ոչ միայն ներկայումս տեսանելի կույտը: Հորիզոնական քարը իր բջիջները բաշխում է \(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-ից Z-ի կամ հակառակը փոխելը մեկ բջիջ լայնությամբ և երկու բջիջ խորությամբ բաց է թողնում: Մանրամասն ցույց է տալիս Z-քարը S-քարի վրա; երկուսն էլ «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\) վիճակները կրկնություն կունենան: Նույն տախտակի և նույն հաջորդ ձևի պատճառով օրինական շարժումները կարող են կրկնվել ցանկացած անգամ. անսահման խաղը պարզապես բացառված է:
Սահմանը նաև հաշվում է տախտակի անհասանելի ձևերը և չի կանխատեսում խաղի գործնական տևողությունը: Burgiel-ի ավելի նուրբ երկրաչափական հաշվարկը տալիս է ավելի փոքր սահմաններ. այստեղ բավարար է վերջավոր \(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\) հավանականությամբ ինչ-որ պահի կհայտնվի մահացու բլոկ, եթե մինչ այդ խաղը չավարտվի: Սա վերաբերում է նաև դրա մասին մտածելու ցանկացած ժամանակի և քարերի ամբողջ հաջորդականության ամբողջական իմացությանը: Սա չի հանգեցնում կարճ գործնական խաղաժամանակի: Միայն չկենտրոնացած, վատ մեկնարկը չի նշանակում պարտություն. Անշուշտ հնարավոր են անակնկալ վերադարձներ: Այսպիսով, մի հուսահատվեք և վայելեք հավերժական խաղը: