Az alábbi feliratot Cooldavee-nek köszönhetjük.
Barátaink sajnos valahol elszámolták magukat, így nem menekültek meg a börtönből. Egy harmadik alkalommal azonban az állami ünnepségek alkalmával új lehetőséghez jutottak.
Az őrök az elnök úr parancsára, ezúttal egy nagy lámpafalat szereltek fel a börtön egyik épületének oldalára. A lámpák négyzet alakban, egymás fölött és mellett helyezkedtek el, hasonlóan egy mátrix elemeihez.
A mátrix minden sorához és oszlopához tartozott egy-egy kapcsoló, amivel az egész sor, illetve oszlop összes lámpáját egyszerre lehetett átállítani: ha a lámpa eddig ki volt kapcsolva, akkor bekapcsolni, és fordíva.
A játék ezúttal az volt, hogy minden rab, aki le tudja kapcsolni az összes lámpát, egy nap kimenőt kap az ünnepségekre. Minden próbálkozás előtt egy őr állította be a lámpákat, de természetesen úgy, hogy a kapcsolgatás sorrendjét a próbálkozó nem látta.
Barátaink ezt a lehetőséget használták ki arra, hogy végre megszökjenek a Lámpák és kapcsolók országából. Milyen algoritmust használhattak?
A kijelző bármely két sorára igaz az alábbi két állítás valamelyike:
a) az egymás fölötti lámpák ugyanabban az állásban vannak bennük;
b) az egymás fölötti lámpák ellentétes állásban vannak bennük.
Kezdetben ez nyilván teljesült, hiszen akkor minden lámpa le volt kapcsolva. A sorok és oszlopok kapcsolgatása pedig nem rontja el ezt a tulajdonságot.
Ezután egy jó megoldás pl. a következő: kapcsoljuk le az első sor minden lámpáját az oszlop kapcsolók segítségével, majd az esetleg fennmaradó, most már teljesen világító, sorokat kapcsoljuk le a sor kapcsolókkal.
Gumi fogaskerék díjat ezúttal nem tudok adni, mert szerintem nem sikerült elég jól megfogalmaznotok a fentieket. Különdíjat érdemel csakazértse szemléltetése, amivel az algoritmus egyszerűen kidolgozható.
Comments are closed.
huh, remélem, most már tényleg sikerül megszökniük… 🙂
Nekem a megérzésem valami átlós irányokat sugall… Este neki állok agyalni, becsszó! 🙂
Vét a minit… Ez nekem így túl egyszerű: Fogja a rab, és vagy lekapcsolja az összes lámpát függölegesen, vagy azokat vízszintesen…
ha arról van szó, ami itt
csakazertse.freeweb.hu/lampak.php
kipróbálható, akkor nem sokan maradnak a börtönben.
hümmm, ezt direkt nekünk csináltad,
Első gondolat:
Elindulok az első soron. Amelyik lámpa világít, annak az oszolpát lekapcsolom, majd az első oszlopon csinálom ugyanezt.
@Thresher: Lehet, hogy jóra gondolsz, de amit írsz az nem jó, vagy legalábbis erősen pongyola a megfogalmazás.
és be is kéne látni, hogy miért működik…
@rusty: Az első gondolatod remekre sikeredett. Most már csak bizonyítani kéne (nem nehéz, de azért kell), hogy ez tényleg minden, bárhogyan összekutyult lámpamátrixra megoldást ad. 😉
Ja vágom, szóval van egy felkapcsolt alakzat…
Tehát: Kell választani egy sarkot, és azt fokozatosan békén kell hagyni. Rusty példáján kiindulva, választok egy sarkot legyen az A1, az A oszloppal ás az 1-es sorral beállítom az A1-et. Megyek tovább le/jobba, így se az A, se az 1-es nem lesz többé kapcsolgatva, ergo az A1-es lámpa már végig úgy marad.
Jön a következő “sarok”, de az ugyanez mint ahol az A1 van, csak ez négy egységnyi négyzet lesz. Tehát a B meg a 2-sel beállítom az A2-t, a B1-et meg a B2-t. Megint lejebb és megint jobbra. Mivel a korábbi sorokra/oszlopokhoz nem nyúlok, így azok maradnak végig az adott állásban. Tehát utána a 9-es négyzet 5 lámpáját kell átkapcsolni, majd a 16-os négyzetből 7-et etc.
De rusty-é az érdem ő előbb írta le.
@Thresher: Azért ez bizonyításnak még kevés. Honnan tudjuk pl. hogy bármilyen előállítható lámpamátrixot vissza tudunk így kapcsolni. Kicsit konkrétabban: honnan tudjuk, hogy a 3×3-as sarok esetén biztosan nem fog kelleni az “A”, “B” vagy az “1”, “2” kapcsoló, és pusztán a “C” és “3” kapcsolókkal ki tudjuk kapcsolni a 3×3-as sarok 5 lámpáját? És ha esetleg úgy adódik, hogy ez mégis sikerül, mi a biztosíték arra, hogy nem jutunk-e így el olyan állapotba, ahonnan nem tudunk eljutni a végállapotba?
A kapcsolók a eljes oszlopot (sort) kapcsolják, emiatt ha úgy kapcsolgarunk, hogy az első sorban minden lámpa le legyen kapcsolva szükségszerű, hogy a többi sorban is azonos állapotban (0 vagy 1) legyenek a lámpák.
Ha nem így lenne, a feladat nem lenne megoldható, valamint a kezdeti állapot csupán a kapcsolók állítgatásával nem lenne elérhető.
Másosik lépésben a viálító sorokhoz tartozó kapcsolókat állítjuk át.
@rusty:
Természetesen az első sorban lekapcsolt lámpákat a világító lámpához tartozó oszlop kapcsolójának állításával érjük el.
Ui.: nem kell ragaszkodni az ‘első sor-első oszlop’-variációhoz. igazából tetszőleges sor és oszlop kiválasztható.