Nalo wale ʻoe ma Tetris no ka mea ʻaʻole ʻoe e pāʻani maikaʻi a hana hewa paha? ʻOiai me ka nui o ka manawa e noʻonoʻo ai, ʻaʻole hiki ke mālama ʻia kahi ʻano pōhaku maikaʻi ʻole. ʻO ka mea hoʻoholo he ʻelima ala haiki a me kahi helu ʻokoʻa. Manaʻo mākou i kahi kahua pāʻani me nā kolamu \(10\) a me nā lālani \(20\) me ka papa ʻole (paʻa): Ua huki kūʻokoʻa kēlā me kēia pōhaku hou a māhele like ʻia mai nā tetrominoe ʻehiku. Loaʻa i kēlā me kēia ʻano ʻehā mau ʻāpana pili. Hiki ke ʻike mua ʻia ka ʻāpana holoʻokoʻa.
ʻO ka ʻoiaʻiʻo o ka pau ʻana o kahi pāʻani, ʻaʻole ia he manaʻo e pau nā ʻano pōhaku i manaʻo ʻia. Hiki ke hoʻokani pau ʻole ʻia ke kaʻina maʻemaʻe o nā pōhaku-O: ʻelima mau ʻāpana i hoʻonoho ʻia ma ka ʻaoʻao o kekahi e holoi i ʻelua lālani a hoʻokaʻawale i ka papa. I loko o 7-Bag, loaʻa i kēlā me kēia ʻeke hui pū ʻia nā ʻano ʻehiku a pau i hoʻokahi; ʻAʻole pili kā mākou manaʻo kūpono i kēia. Ma Pehea e Nalo ai ma Tetris, hōʻike ʻo Heidi Burgiel i kahi kaʻina ʻaʻole kōkua ka pāʻani maikaʻi: \(S,Z,S,Z,\ldots\) .
ʻO S a me Z nā kiʻi aniani, ʻaʻole nā ʻano ʻokoʻa o ka pōhaku hoʻokahi. Hōʻike ka wehewehe ʻana i ka manaʻo geometric a mākou e hōʻike nei ma ke ʻano he hōʻoiaʻiʻo ma ke kūʻē. ʻO ka ʻōlelo maopopo "i kekahi manawa ʻike wale ʻia nā pōhaku Z a ʻaʻohe lālani e nalowale me lākou" he hewa. ʻElima wale nō mau pōhaku S i hoʻonoho ʻia ma luna o ke poʻo e hāʻawi i kēia hoʻonohonoho ma luna o kahi papa kaʻawale. ʻO nā hua palapala hoʻokahi e hōʻike ana i ka pōhaku hoʻokahi; Hōʻailona nā kiko i nā hakahaka kaʻawale:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eUa pau a holoi ʻia ka lālani waena. Inā hoʻohālikelike ʻoe i ka hoʻonohonoho ʻana, loaʻa iā ʻoe ka laʻana like no nā pōhaku-Z. ʻO ka pilikia ʻaʻole ka holoi ʻana i nā lālani pākahi, akā ʻo ka nīnau inā hiki iā ʻoe ke hoʻomalu i nā imbalances āpau e kū mai ana ma kahi helu palena ʻole o nā pōhaku. E helu kākou i nā kolamu mai \(1\) a i \(10\) . Ma ka \(b_i\) hōʻike mākou i ka huina o nā pūnaewele hou a pau i waiho ʻia ma ke kolamu \(i\) , me nā mea i holoi ʻia ma hope.
\(h_i\) helu i na pohaku S a i ole Z paha me ke kolamu waena \(i\) , \(v_i\) pohaku ku pono ma na kolamu \(i\) a me \(i+1\) . Hoʻopaʻa nā helu helu i ke kaʻina o ka pāʻani, ʻaʻole wale ka waihona ʻike ʻia i kēia manawa. Hoʻokaʻawale ka pōhaku i kona mau pūnaewele i ka ratio \(1,2,1\) ma luna o ʻekolu kolamu, he pōhaku kū i ka ratio \(2,2\) i ʻelua kolamu. Loaʻa i nā kiʻi aniani ʻelua ke kaulike kolamu like. Inā hoʻohui ʻoe i kēia mau haʻawina ma nā wahi āpau, loaʻa iā ʻoe no kēlā me kēia kolamu:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Ma waho o ka papa hoʻonohonoho mākou i nā helu helu āpau i \(0\) ; ʻo kekahi \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Ke pale nei kēia kuʻina lihi i ke koena mai ka helu ʻana i nā pōhaku e ʻoi aku ma mua o ka lihi o ke kahua pāʻani. ʻAʻole ʻae ʻia ia mau wahi i kā mākou kumu hoʻohālike. Inā hoʻomaka ke kaʻina S/Z e noʻonoʻo ʻia ana ma ka papa i hoʻopiha ʻia, e ʻae ʻo \(a_i\) nā pūnaewele i noho mua ʻia a me \(c_i\) nā pūnaewele i noho ʻia i kēia manawa ma ke kolamu \(i\) . Ma hope o \(R\) holoi ʻia nā lālani:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
I ka wā e holo ana ka pāʻani, aia nā \(a_i,c_i\) ma waena o \(0\) a me \(20\) . No laila, pili ka \(|b_i-b_j|\leq40\) . Inā haʻahaʻa ka papa mua \(20\) . Lawe ʻia kēlā me kēia lālani i holoi ʻia i hoʻokahi cell mai kēlā me kēia kolamu. ʻO ia ke kumu e hoʻemi ʻia ai ka helu o nā lālani i holoi ʻia i ka hoʻohālikelike ʻana i ʻelua kolamu, ʻoiai inā e ulu mau nā helu helu o nā cell set. Helu ʻoe i nā cell i hoʻopaʻa ʻia ma kahi o nā kiʻekiʻe hoʻopaʻa; ʻOkoʻa nā nui ʻelua i ka wā e pili ana i nā lua. Inā kākau mākou i kēia palena ma ke ʻano he \(D\) , ma ka ʻaoʻao hema a ʻākau paha:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
No nā kolamu i loko, hoʻohui mākou i ʻelua ʻokoʻa kolamu i kaupalena ʻia: \(b_4-b_3\) a me \(b_2-b_1\) ma ka hema, \(b_7-b_8\) a me \(b_9-b_{10}\) ma ka ʻākau. Ma hope o ka hoʻokomo ʻana i ke koena kolamu, hoʻopau pololei nā helu ma waena. Ke waiho nei kēia i nā haʻawina maikaʻi ʻole ma kēlā me kēia ʻaoʻao hema, i hoʻopaʻa ʻia e \(2D\) . Hāʻawi kēia iā mākou i kahi palena kiʻekiʻe no nā helu hoʻonohonoho ponoʻī no nā hui ʻelua i loko:
$$\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}$$
Inā mākou e hoʻohui i nā ʻano like ʻole ʻehā, helu ʻia kēlā me kēia pōhaku i hoʻokahi pololei. ʻO nā ʻano ʻehā o ka hoʻokomo ʻana i ke ala kuamoʻo e loaʻa i nā coefficient maikaʻi. ʻEkolu kolamu o nā pōhaku ākea a no laila ʻaʻole kūpono loa i kekahi o nā ala kolamu ʻelua i manaʻo ʻia ma hope. No nā pōhaku kūpaʻa, hoʻokaʻawale mākou i nā ala e like me ke kolamu hema. No ka mea ʻaʻole hewa nā helu helu āpau, ʻaʻole hiki ke hoʻopau ʻia kekahi o kēia mau haʻawina e kekahi:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
No laila, hiki ke hoʻokomo ʻia nā kau ʻeleʻele a me ke kū pololei me ke kolamu hema pololei i ka lōʻihi o \(120\) mau manawa ma kahi papa kaʻawale a i ʻole \(240\) mau manawa ma kekahi papa i hoʻopiha mua ʻia. He palena kiʻekiʻe kēia, ʻaʻole he koi e hiki ke hoʻokō maoli ʻia. I kekahi hihia, ʻaʻole hiki ke hoʻohana pinepine ʻia kēia mau neʻe evasive. I kēia manawa, manaʻo mākou hiki iā ʻoe ke pāʻani i ke kaʻina ʻokoʻa no ka pau ʻole.
Ma hope o ka helu hope loa o ka neʻe ʻana i nā neʻe evasive, hiki ke hoʻokomo wale ʻia ma nā ala paʻa ʻelima: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Kūlike nā ʻano like ʻole i kekahi i kekahi ma ke ʻano he ʻanuʻu: ʻo ka lalo e hui me ka piko like o ka pōhaku mua. ʻO ka hoʻololi ʻana mai ka S a i ka Z a i ʻole ka hoʻololi ʻana, waiho ʻia kahi āpau i hoʻokahi keena ākea a ʻelua mau cell hohonu. Hōʻike ka kikoʻī i kahi pōhaku Z ma luna o kahi pōhaku S; ʻo ka "o" ʻelua e hōʻailona i ke āpau:
.Z
ZZ
Zo
So
SS
.SʻAʻole hiki i kekahi pōhaku kū i ke ala like ke hoʻopiha i kēia āpau: ʻo kona kolamu lua e hui pū me nā keʻena e noho kokoke ana. ʻAʻole kōkua ka holoi ʻana i nā lālani inā ʻaʻole i paʻa nā lālani ʻelua. Pono ka hoʻoponopono ʻana i kekahi o nā ala keʻa a i ʻole nā hoʻonohonoho ʻāpae. Ma hope o ka neʻe ʻana hope loa, mau ia mau āpau. ʻAʻole hiki ke ala aʻe ma luna o kahi papa palena ʻole ka helu palena ʻole o nā āpau hou.
ʻO ka hopena, hiki ke loaʻa i kahi helu palena o nā loli i ke ʻano ma nā ala. ʻAʻole hiki ke hoʻololi i kēia ala kaʻawale: ua waiho mua kāu pōhaku S a i ʻole Z i kahi āpau kolamu ma ka papahele ʻaʻole hiki ke pani ʻia e ka pāʻani ala maʻemaʻe. I loko o kahi pāʻani i manaʻo ʻia ʻaʻole pau ʻole, pono e paʻa i kēlā me kēia alahele ka helu ʻole o nā pōhaku. Inā ʻaʻole i hoʻopā ʻia kahi alahele i kekahi manawa, hiki ke hoʻokomo ʻia kahi helu palena o nā cell ma nā ala i koe ma muli o nā koena kolamu i kaupalena ʻia.
No laila, hiki mākou i kahi manawa e noho mau ai nā ala ʻelima a paʻa i kahi palapala. Mai keia la aku, helu kakou \(t\) pohaku hou aku a me \(n_j(t)\) ka helu ma ke ala \(j\) . Hāʻawi kēlā me kēia mau pōhaku i ʻelua keena i kēlā me kēia kolamu o kona ala. Ma muli o ka hana like ʻana o nā holoi lālani i nā kolamu a pau, ua kaupalena ʻia nā ʻokoʻa \(n_j(t)-n_k(t)\) . I ka wā lōʻihi, pono e paʻa i kēlā me kēia ala ʻelima ka hapalima o nā pōhaku:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Inā mālama ʻia \(k\) o nā ala ʻelima no nā pōhaku-S, ʻo kā lākou ʻāpana e puni i \(k/5\) . Eia naʻe, ma ke kaʻina ʻokoʻa ʻo ia ka \(1/2\) : i kēlā me kēia prefix, ʻokoʻa nā helu o nā pōhaku S a me Z ma ka nui o \(1\) . ʻO ka māhele ʻana o nā alahele e hoʻokō i nā ʻāpana ʻelua i ka manawa like. Eia naʻe, ʻaʻole hiki ke hōʻike ʻia ka hapa o ka hapalua ma ke ʻano he huina o ka hapalima holoʻokoʻa. ʻO kēia kahi e hui pū ai ka alapine o nā ʻano like ʻole a me ka helu ʻē aʻe o nā mele i hoʻohana ʻia. Pono kēlā:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
ʻO ka helu o nā alahele he helu helu. Hoʻopau kēia kū'ē i ka manaʻo o kahi pāʻani pau ʻole. Hōʻike pū ka hoʻopaʻapaʻa i ke kumu o ka laula o ka papa i ʻāpana o ia: Me nā kaʻaahi ʻehā, ʻaʻole e kāpae ʻia ka māhele ʻana i ʻelua mau kaʻaahi S a me ʻelua Z e kēia kūʻē. No ka hōʻoiaʻiʻo ʻole pono mākou i ka lōʻihi o ka poloka palena \(N\) e alakaʻi i ka nalowale me ka nānā ʻole i ka papa o kēia manawa. "Holo nā hoʻolālā āpau i kekahi manawa" ʻaʻole lawa.
Hoʻopili ka like ʻana mai ka helu palena o nā mokuʻāina hiki. Ma hope o kēlā me kēia hoʻokomo ʻana, aia ka nui o \(2^{200}\) mau ʻano noho. Aia kekahi ʻike e pili ana inā ʻike ʻia ʻo S a i ʻole Z ma hope aʻe, ʻo ia hoʻi ka palena o nā mokuʻāina \(2^{201}\) . Inā ola ʻoe i nā pōhaku \(N=2^{201}\) , ʻōlelo ka \(N+1\) ma mua a ma hope o kēia mau neʻe ʻana he hana hou. Ma muli o ka papa like a me ke ʻano like aʻe, hiki ke hana hou ʻia ka neʻe ʻana o ke kānāwai ma waena o nā manawa he nui: ua kāpae ʻia ka pāʻani pau ʻole.
E helu pū ana ka palena i nā kumu papa hiki ʻole ke loaʻa a ʻaʻole wānana i ka lōʻihi o ka pāʻani pono. Hāʻawi ka helu geometric maikaʻi a Burgiel i nā palena liʻiliʻi; maanei ua lawa ka \(N\) . Pili ia i nā hana mua i ʻae ʻia a me nā māhele ʻelua o ke kaʻina S/Z. E hoʻoheheʻe kākou i ke kaʻina like ʻole i nā poloka ʻokoʻa o ka lōʻihi \(N\) . ʻO kēlā me kēia poloka ke kaʻina kikoʻī \(S,Z,S,Z,\ldots\) me ka likelika \(q=7^{-N}>0\) . Kūʻokoʻa nā poloka. No laila, ʻaʻohe o nā poloka \(m\) mua i loaʻa kēia kaʻina:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
No laila me ke kūpono \(1\) e ʻike ʻia kahi poloka make i kekahi manawa, ke ʻole e pau ka pāʻani ma mua o ia manawa. Pili pū kēia me ka nui o ka manawa e noʻonoʻo ai a me ka ʻike piha o nā hopena. ʻAʻole kēia i hopena i ka manawa pāʻani pōkole, a ʻo ka hoʻomaka ʻino wale ʻana ʻaʻole ia he manaʻo e lanakila: Hōʻike ka animation ma lalo nei i ʻelima mau ʻano huikau i helu mua ʻia, hiki i kēlā me kēia i kahi papa hakahaka ma hope o ʻeiwa mau wahi hale kiaʻi i hoʻololi ʻole ʻia. ʻAʻole ʻo ia he bot Tetris universal.