Jag har nyligen fått ett nytt delintresse (ett intresse inbakat i ett mer generellt intresse). Det är egentligen en liten samling matematik problem.

Då jag under de senaste veckorna spelat en del tetris (och upptäckt att jag inte är usel på det) har frågan slagit mig: Finns det någon sekvens (med "klossar" som ramlar ned) som gör att spelet blir omöjligt att klara? Frågan är rätt svår så man kan och bör dela upp den i delproblem som är lättare att lösa. Jag har kommit fram till följande familj av problem: givet en godtycklig bredd (normal bredd är 10) och klossar av godtycklig men mindre storlek (normal storlek eller antal celler i varje kloss är 4), finns det då en upprepning av samma kloss så att man så småningom kommer att förlora? I det vanliga fallet är jag bara osäker grön och röd i den länkade bilden. De andra går bra dvs svaret på frågan är negativt. Om bredden är udda däremot så blir svaret positivt på den gula klossen.

http://upload.wikimedia.org/wikipedia/commons/3/39/Tetrominoes_IJLO_STZ_Worlds.svg

Jag gör tillägg senare för jag är jättetrött nu. Om ni har idéer på hur man löser det här så posta gärna!

Upprepning av samma kloss i normalfallet är löst. Med rätt strategi klarar man det och svaret på frågan blir då negativt.

Någon med tålamod får gärna prova sekvensen 5 gröna 5 röda upprepa. Finns misstanke om den kan vara en omöjlig sekvens.

En fråga om rekursion för kombinatorik nördar: Hur många klossar av "tetris typ" finns det som består av k celler? Jag känner ännu inte till någon rekursiv formel.

Jag skissade lite på papper vad som skulle hända om man fick lika många gröna och röda, och vid en första anblick ser det omöjligt ut.
En snabb googling gav mig detta: http://www.liacs.nl/~kosters/tetris/tot.pdf
Jag sitter dock på jobbet så jag kan inte kolla närmare på det nu.

Ang. block-kombinationer så beror det väl lite på hur man räknar... Ska man t ex räkna långeman (fint namn va?) som 1, 2 (h/v) , eller 4 (h/v+dubletter) kombinationer? Det finns säkert ett av de sätten att räkna som är mer naturligt om man sätter sig in i beräkningarna.

Krake skrev:En fråga om rekursion för kombinatorik nördar: Hur många klossar av "tetris typ" finns det som består av k celler? Jag känner ännu inte till någon rekursiv formel.

Jag är både kombinatoriknörd (fast ytterligt amatörmässig) och särskrivningsallergiker (men jag tar piller) .

Intressanta grejer det här. Just den citerade frågan borde du ha talat med uniqueNr5 med, han är dock tyvärr inte aktiv längre. Men nånstans har jag en wikilänk från honom, om detta problem som ingår i ett olöst partitionsproblem - vågar jag påstå. Ska kolla senare.

jonsch skrev:Jag är både kombinatoriknörd (fast ytterligt amatörmässig) och särskrivningsallergiker (men jag tar piller) :wink: .

I bland är det svårt att läsa samman satta ord så då kan det vara lättare om man delar upp dem. Var för är det så? Jo! Det är helt enkelt jobbigt att läsa långa rader av samman satt text utan sär skrivning. Jag kan ibland vara lite av en i hop skrivnings allergiker men jag kanske har en liten liten släng av dysleksi också.

Krake skrev:I bland är det svårt att läsa samman satta ord så då kan det vara lättare om man delar upp dem. Var för är det så? Jo! Det är helt enkelt jobbigt att läsa långa rader av samman satt text utan sär skrivning. Jag kan ibland vara lite av en i hop skrivnings allergiker men jag kanske har en liten liten släng av dysleksi också.

Har man en släng av dyslexi kanjag tänka mig att det är lättare att läsa uppstyckade ord. Men för mig är det precis tvärtom. Och ärven skriva är jobbigt för mig om jag tvingas skriva isär. Så jag antar att vi får stå ut med varandras skrivsätt, helt enkelt.

Jag är inte så ointresserad av problemet i sig men det faller antagligen in under ämnet polyominoes.
Solomon Golomb är matematikern som myntade detta som senare Populariserades av Martin Gardner.

Man betraktar diskreta geometriska figurer som är ekvivalenta under rotation.
Det finns ingen känd formel för antalet polyominoes av en given storlek k.

Tetris är alltså, om jag minns rätt. Polyominoes med k=4.

Problemet att täcka ytor med dessa är väl en sorts "tiling" problem.
Det har studerats i viss utsträckning av bl.a. matematikerna ovan.
Men som sagt. Det är inte frågan om att ha exakta formler att dra fram ur rockärmen för det generella fallet.

När det gäller jonsch referens till partitioner av heltal så är det ett helt annat ämne.

Vad gäller din ursprungliga fråga så säger min intuition mig, utan att ha spelat tetris på flera år eller någonsin varit intresserad av det, att det inte finns någon sådan omöjlig sekvens.
Det är snarare bara så att "mänskliga faktorn" gör att misstagen ökar ju högre hastigheten för spelet är och ju längre tiden går.

Däremot kan man man ändra förutsättningarna för spelet och säga så här:
Givet ett godtyckligt "tetris-utgångsläge", finns det en konstellation och en sekvens av tetrominoes
(polyominoes av storlek k=4) som innebär oundviklig förlust.

Där skulle jag gå baklänges. Från en godtycklig förlust vad är alla tillstånd (konfigurationer) av
tetrominoes tilings (täckningar) som skapats från ett håll (uppifrån och ner).

Det borde inte vara så svårt att skapa en algoritm som listar alla sådana konfigurationer.
Dvs Du går baklänges från en förlust situation och genererar alla möjliga spelscenario konfigurationer.

Då kan du besvara frågan empiriskt genom att hitta ett exempel som bekräftar existens av en sådan sekvens Givet ett taskiskt utgångsläge som man skapat genom att göra en massa misstag.


http://en.wikipedia.org/wiki/Polyominoes

Om det finns en omöjlig sekvens eller inte lär väl inte bara bero på bredden utan också på höjden, dvs hur högt man får bygga innan man har misslyckats? Om höjden är tillräckligt låg (t.ex. 1) går det inte att klara spelet.