Kevésbé formálisan:
Adott egy téglalap alapú terem, mely függőlegesen négyzetalakú cellákra van osztva. E cellák némelyikében (akár az összesben) lámpák vannak. Minden olyan cellában, amelyben van lámpa, van egy kapcsoló is. E kapcsoló e lámpához tartozik, viszont viselkedése nem szokványos: az aktuális lámpa állapotán kívül mind a négy élszomszédjának állapotát is megfordítja (ha az adott élszomszéd cellában van lámpa, illetve ha beszélhetünk négy élszomszédról, azaz nem falnál, illetve sarokban vagyunk).
A lámpák kezdetben fel és le is lehetnek kapcsolva (adott egy kapcsolási állapot). A cél az, hogy az összes lámpát lekapcsolt állapotba helyezzük.Formálisan:
Adott egy n×m-es { -1 ; 0 ; 1 } feletti mátrix. A mátrix egyes mezői 0 értékűek, ha az adott cellában nincs lámpa, -1 értékűek, ha van lámpa, és az le van kapcsolva, 1 értékűek, ha van lámpa, és az fel van kapcsolva.
Egy lámpa állítása a következő módosítást eszközöli a mátrixon: legyen a lámpa két koordinátája i és j. A lámpa kapcsolásának hatására az (i;j), (i;j-1), (i+1;j), (i;j+1), (i-1;j) cellák értéke (-1)-szeresére változik, ezek létezése esetén (azaz kivéve: i ∈ { 1 ; n } V j ∈ { 1 ; m } ).
A dilemma:
- Döntsük el, hogy lekapcsolható-e az összes lámpa!
- Adjunk olyan kapcsolási sort, amely az összes lámpát lekapcsolja!
- Adjuk meg ezek közül a legrövidebbet, ha több ilyen van, akkor azok közül valamelyiket.
Amire eddig jutottam:
Könnyen belátható, hogy a { -1 ; 0 ; 1 } a hagyományos Z-n értelmezett * (szorzás) műveletre zárt: hiszen -1 * 0 = 0 * 0 = 0 * 1 ; 1 * 1 = 1 ; -1 * -1 = 1 ; 1 * -1 = -1 . (Következésképpen ha a mátrix sorait vagy oszlopait { -1 ; 0 ; 1 } -beli vektorral szorozzuk, akkor { -1 ; 0 ; 1 } -beli mátrixot kapunk eredményül. Az is könnyen belátható, hogy { -1 ; 0 ; 1 } jólrendezett a Z-n értelmezett jólrendezésre, ami triviális, hiszen { -1 ; 0 ; 1 } részhalmaza Z-nek. Tehát a * szorzás műveletet teljes nyugodtsággal használhatjuk multiplikatív műveletnek, a > relációt pedig jólrendezési relációnak.
Én úgy látom, hogy a kapcsolgatást egy másik mátrixszal lehetne "nyilvántartani", modellezni. Legyen adott így egy n×m-es { 0 ; 1 } feletti mátrix, mely kezdetben nullmátrix. Egy (i;j) lámpa kapcsolása a mátrixban az (i;j) cellán hajtja végre a + műveletet, definiáljuk +(0) := 1 ; +(1) := 0 módon. Triviális, hogy ha a kapcsolási folyamat során egy kapcsolóhoz többször (kétszer) is hozzányúlunk, az a végeredmény szempontjából olyan, mintha egyszer sem nyúltunk volna hozzá, azaz ekkor csináltunk két fölösleges lépést. (Mivel a végső cél a legrövidebb út megkeresése, érdemes így szűrni a biztosan fölösleges lépéseket.)
A lámpák ( M(i;j) ∈ { -1 ; 1 } ) számának maximuma m*n (ekkor mindenhol van lámpa), tehát a lehetséges különböző kapcsolási utak (bárhová is vezetnek) maximuma 2^(m*n), ami banális. Azonban ezeknek igen csekély számú interpretációja fog az "összes lámpa lekapcsolásához" vezetni. Ezek közül aztán pedig talán ki lehetne választani a legrövidebbet (aminek maximális hossza n*m).