Megfejtené valaki ezt a lámpás-kapcsolós feladatot?

Ez a feladat nagyon hasonlít a "Lights Out" nevű játékhoz.

A válasz egyszerű lesz, csak hosszú hozzá a bevezetés. Meg a végén a magyarázat is hosszú :)

Jelöljük a lámpák állapotát a 0 illetve 1 számmal; ha világít, akkor 1. A teljes kör így 15 szám lesz.

Egy lépés során ellenkezőjére váltjuk 3 szomszédos lámpa állapotát. A lépést jelöljük azzal a számmal, amelyik a 3 lámpa közül a középső. Mondjuk a "3" nevű lépés során azok a lámpák váltanak állapotot, ahol 1-et írtam:

0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

Az "1" nevű lépés során pedig ezek:

1 1 0 0 0 0 0 0 0 0 0 0 0 0 1

hiszen egy körben van ez a 15 szám.

Felírhatjuk az összes lépést egy mátrixban:

1 1 0 0 0 0 0 0 0 0 0 0 0 0 1

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1

1 0 0 0 0 0 0 0 0 0 0 0 0 1 1

Legyen ez az A mátrix.

Ennek a mátrixnak az n-edik sora azt mutatja, hogy az "n" nevű lépés során az n-edik lámpát és a két szomszédját váltjuk át.

Ha meglépjük mondjuk a "3", "5" és "8" nevű lépést, akkor annak a három sornak a lámpái váltanak:

0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 0 0 0 0 0 0

Ezt felírhatjuk egyetlen számsorként is: ha páros számszor módosul egy lámpa állapota, akkor változatlan marad, ezért oszloponként modulo 2 kell összegeznünk az előző 3 sort:

0 1 1 0 1 1 1 1 1 0 0 0 0 0 0

Ha egy sorvektorral jelöljük azt, hogy melyik lépéseket lépjük meg (1 van ott, amit meglépünk), akkor a fenti 3 lépést így írhatjuk fel:

x = (0 0 1 0 1 0 0 1 0 0 0 0 0 0 0) vagyis a 3, 5 és 8 oszlopban van csak 1.

A megváltozó lámpákat pedig ez a mátrixszorzás (modulo 2) eredménye mutatja:

x·A

A lámpák állapotát is sorvektorral írjuk fel. Ha kezdetben a lámpák s állapotban vannak, akkor az x lépések után a t állapot ez lesz:

s + x·A = t

Itt is modulo 2 aritmetikával kell érteni a mátrixszorzást is meg a vektor-összeadást is.

Ha az s állapotból a t állapotba akarunk eljutni, ami jelenleg ezek:

s = (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

t = (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

akkor ez az x lépéssorozat kell hozzá:

x·A = t − s

(A kivonás helyett lehet összeadást is csinálni, hisz modulo 2-ben azok eredménye egyforma.)

Itt a t − s jelenti a változást, hogy mely lámpák állapota kell megváltozzon. Jelöljük ezt a b sorvektorral:

x·A = b

x = b·A⁻¹

Vagyis ha b változást akarunk elérni, akkor y·A⁻¹ lépéseket kell csinálni.

(A lineáris algebrában inkább oszlopvektorokat használnak, amikkel fordított irányban kell a mátrixszal szorozni, de ez is pont ugyanaz. Írhattam volna oszlopvektorokat is... semmi lényegesen nem változtat.)

Ennyi volt a bevezetés.

Vagyis a lényeg, hogy invertálnunk kell az A mátrixot. Ezt mondjuk Gauss eliminációval csinálhatjuk meg, persze modulo 2 aritmetikával. Felírjuk ezt a 15×30-as márixot tehát:

1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 | 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 | 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 | 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 | 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 | 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 | 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 | 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 | 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 | 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

A Gauss elimináció lépései után ezt kapjuk: (nem kézzel csináltam, írtam hozzá egy kis programot)

1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 | 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0

0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 | 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 | 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 | 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 | 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 | 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0

0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 | 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 | 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 | 1 1 0 1 1 0 1 1 0 1 0 1 1 0 0

0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 | 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 | 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 | 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

Vagyis a mátrix nem invertálható, a rendje csak 13 (lett két csupa 0 sor a bal oldal alján).

További magyarázat:

Attól, hogy nem invertálható a mátrix, még nem kell kétségbe esni. Ez csak azt jelenti, hogy az egyenletrendszer az adatok (b) függvényében vagy nem oldható meg, vagy ha igen, akkor több megoldás (x) is van. Úgyhogy még nem veszett el feltétlenül minden. Ha több megoldás is van, akkor érdekes az a kérdés is, hogy melyik a legrövidebb.

A mátrix rendje kisebb a méreténél, ezért függő változók vannak benne (most 2). A függő változók most azt jelentik, hogy a lámpák nem függetlenek egymástól. Nincs olyan lépéssorozat, ami csak egyetlen egy lámpa állapotát változtatná meg. Például a felülről második sor azt jelenti, hogy az

x = 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0

lépéssorozat (második sor jobb oldal) hatására megváltozik a második valamint az utolsó előtti lámpák állapota:

b = 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0

(bal oldal).

(Azért a sorokat kell nézni az oszlopok helyett, mert sorvektorokkal dolgoztunk.)

A fenti mátrixból most már az is kiolvasható, hogy nincs olyan lépéssorozat, ami az egyetlen égő lámpánkat oltaná csak el. Ami azt is jelenti, hogy nem tudjuk mind a 15 lámpát bekapcsolni (amit pl. úgy érhettünk volna el, hogy kikapcsoljuk az egy szem égő lámpát, aztán minden harmadik lépéssel mindegyiket bekapcsoljuk. Ami persze nem a legrövidebb megoldás lenne, de hát ha nincs egy sem, akkor legrövidebb sincs.)

Ha induláskor két lámpa égne amik között két leoltott lámpa van, akkor lenne megoldás. És sok más esetben is lenne megoldás...

A feladat végül is ennyi volt, de van még érdekesség. Az utolsó 2 sornál a jobb oldal azt jelenti, hogy az

i₁ = (1 1 0 1 1 0 1 1 0 1 1 0 1 1 0)

és

i₂ = (1 0 1 1 0 1 1 0 1 1 0 1 1 0 1)

lépések nem változtatják meg a lámpák állapotát, szóval ezek a transzformáció egységelemei. Természetesen a triviális egységelem is létezik:

i₀ = (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

Van még egy negyedik egységelem is: i₁+i₂ (ahol a + megint csak modulo 2 értendő):

i₃ = (0 1 1 0 1 1 0 1 1 0 1 1 0 1 1)

Ezek az egységelemek azt jelentik, hogy ha találunk egy x lépéssorozatot, mint megoldást egy adott kezdeti lámpaállásra, akkor x+i₁, x+i₂ és x+i₃ is megoldások. Több megoldás pedig nem létezik. A legrövidebb megoldást tehát úgy találhatjuk meg, hogy kiszámoljuk ezt a hármat is, és a négyből a legrövidebbet választjuk.

Kérdés még, hogy milyen kezdeti lámpaállások (pontosabban lámpaváltozások) oldhatóak meg. A Gauss elimináció végeredményéből ez is leolvasható: azok, amik előállíthatóak a bal oldali mátrix néhány sorának az összegeként. Az utolsó 2 oszlop kivételével a többi 1-1 lámpát érint csak, vagyis az első 13 lámpa pontosan beállítható, az utolsó 2 pedig kijön valamilyenre.

---

Megjegyzés:

Az egységelemeket egyszerű végiggondolással, mátrixinvertálás nélkül is ki lehet számolni:

- Triviális, hogy az 100100100100100 egy negatív egységelem, minden lámpát az ellenkezőjére vált.

- Ugyanígy ennek 1-gyel illetve 2-vel eltoltja is negatív egységelem.

- Mindhárom negatív egységelem összege is negatív egységelem, hisz páratlanszor ellenkezőjére váltja a lámpákat. Ez a negyedik az 111111111111111.

- Bármely két negatív egységelem összege (modulo 2) pozitív egységelem lesz. Ebből kijön a 4 egységelem.

(Hosszasabban azt is be lehet látni ilyen elemi eszközökkel is, hogy nincs több egységelem...)

Ha nem 15 lámpa van, akkor a mátrix másmilyen lesz, ezért az inverze is máshogy alakul. Így hat rá a méret. (Most nincs nálam a program, amit írtam, de majd érdekességképpen kipróbálom...)

Parsze ha 8-adikos feladat, akkor nem így kell csinálni. Nem jut viszont eszembe jobb, mint hogy ki kell próbálni a lehetséges kapcsolgatásokat, valahogy így:

A kapcsolgatást (vagyis 3 szomszédos átkapcsolását) egy $ fogja jelenteni, a nem kapcsolgatást *. Az égő lámpának 1, a nem égőnek 0 a jele. A felső sor a kiinduló lámpaállás az eleve égő lámpa körül, a második a kapcsolgatások, a harmadik pedig a kialakult lámpaállás.

Mivel egy kapcsolgatás 3 lámpára hat, ezért ahhoz, hogy az eleve égő lámpa végül égve maradjon, abban a hármasban, aminek ő a középpontja, páros darab kapcsolgatásnak kell lennie.

Kiindulunk ebből a hármasból, aztán szélesítjük a kapcsolgatásokat, hogy egyre több lámpa legyen bekapcsolva. Ugyanazon a helyen többször kapcsolgatni nincs értelme, mert a páratlan kapcsolgatást helyettesíthetjük egyetlen eggyel, ezért tudjuk ily módon felírni azt, hogy milyen műveletet kell csinálni egy adott helyen.

A) eset: Nem történt kapcsolgatás a kiinduló 3 helyen:

010

***

010

Ahoz, hogy a fenti szélső két lámpa égjen, mindkét irányban kapcsolgatással kell szélesíteni, más lehetőség nincs.

0001000

  $***$

1111111

Ahhoz, hogy a $-ok alatti két lámpa égve maradjon, muszáj nem kapcsolgatni tovább:

0001000

*$***$*

1111111

A két szélső égő lámpa miatt továbbra sem lehet kapcsolgatni:

000010000

**$***$**

011111110

Most viszont már muszáj:

0000001000000

  $**$***$**$

1111111111111

A szélső $ alattiak miatt nem szabad kapcsolgatni:

0000001000000

*$**$***$**$*

1111111111111

Ez így már 13 lefixált kapcsolási hely, 13 égő lámpa, még 2 nem égő van a körben.

Azokat viszont sehogy sem lehet átkapcsolni a maradék 2 hellyel úgy, hogy ki ne aludjon más. Tehát ezen az ágon nincs megoldás.

B) eset: 2 kapcsolgatás történt szimmetrikusan a kiinduló hármasban:

00100

  $*$

11111

Ahhoz, hogy a $-ok alatti két lámpa égve maradjon, muszáj nem kapcsolgatni tovább:

00100

*$*$*

11111

Nem írok tovább hosszú magyarázó szöveget, hasonlőan megy, mint eddig:

0001000

**$*$**

0111110

00000100000

  $**$*$**$

11111111111

00000100000

*$**$*$**$*

11111111111

0000001000000

**$**$*$**$**

0111111111110

Már csak 2 hely maradt ki, és van 4 nem égő lámpa. Most sincs megoldás.

C) eset: 2 kapcsolgatás a kezdeti 3 helyen, de nem szimmetrikusan:

00100

  $$*

10110

(A fordított irányú aszimmetrikus eset ennek a tükörképe.)

A bal oldali $ alatti lámpa miatt balra kapcsolgatással kell szélesedni. A jobb oldalon viszont muszáj nem kapcsolgatni a * alatti 1 miatt:

0001000

  $$$**

1011100

Mindkét irányban kapcsolgatás kell:

000010000

  $$$$**$

101111111

Balra mindig visszaalszik egy lámpa, ezért mindig kapcsolgatás kell, jobbra pedig **$ szekvencia látszik az egyetlen megoldás lenni, de azért nézzük egyesével.

00000100000

  $$$$$**$*

10111111110

0000001000000

  $$$$$$**$**

1011111111100

000000010000000

  $$$$$$$**$**$

101111111111111

Még van 2 fixálatlan kapcsolgatási hely, és a 15 lámpa közül egyetlen egy nem égő van. Azt az egyet nem lehet átkapcsolni.

---

Hát, jő hosszú lett, de hátha valaki kitalál egy frappánsat...