lamppujen sammutus (modulo 2)

Tässä ratkaisun hahmotelma:

Tämä on lineaarialgebran ongelma kunnassa Z/2Z. Tässä kunnassa yhteenlasku on ekvivalentti XOR-operaation kanssa.

Siinä pitää ottaa kantavektoreiksi numero i n-pituiset vektorit, joissa on tietyt alkiot ykkösiä ja loput nollia. Nyt jos nämä vektorit virittää annetun lampputilan, ratkaisu on olemassa, muuten ratkaisua ei ole.

Siten optimaalisen kytkinpainallisten sarjan löytäminen on yhtäpitävä sen kanssa, että annettu alkutila voidaan esittää kantavektoreiden lineaarikombinaationa. Uskoisin, että tämän voi tehdä Gaussin eliminointimenetelmällä järkevässä ajassa, kun matriisissa on niin paljon nolla-alkiota.

Katso myös http://stackoverflow.com/questions/30006809/finding-minimum-number-of-presses-to-shut-down-lamps

Näyttää tarvitsevan minulta jonkin verran syvempää matematiikkaan perehtymistä jos aion tuota ratkaista.

Tuossa tosiaankin ei tarvita kuin ykköstä ja nollaa (Yhtä nappulaa tarvitsee painaa joko kerran tai ei kertaakaan) sekä niiden aritmetiikan.

Olisiko tuollainen esitys?
0 ⊕ k2 ⊕ k3 ⊕ k4 = 1
k1 ⊕ 0 ⊕ k3 ⊕ k4 = 1
k1 ⊕ k2 ⊕ 0 ⊕ k4 = 1
k1 ⊕ k2 ⊕ k3 ⊕ 0 = 0

Kokeilin kärsimättömänä tässä vaiheessa ohjelmointiputkan esimerkkiä tavallisella yhteenlaskulla ja matriiseilla. (Kuusi lamppua ja kytkintä, valot 1 ja 2 palavat alussa)


|1 1 1 0 1 1| |k1 | |1|
|1 1 1 1 0 1| |k2| |1|
|1 1 1 1 1 0| |k3| |0|
|0 1 1 1 1 1| |k4| |0|
|1 0 1 1 1 1| |k5| |0|
|1 1 0 1 1 1| |k6| |0|

Tuosta D=5 eli 5 mod 2 = 1
Dk1,Dk2,Dk3,Dk6 = 2 eli 2 mod 2 = 0
Dk4 ja Dk5 ovat -3 eli -3 mod 2 = -1 (miksi miinus?)

Tehtävän ratkaisu oli painikkeiden 4 ja viisi painaminen!

Voiko tuosta varovaisesti päätellä että voi käyttää normaaleja laskusääntöjä, kunhan determinanteissa ottaa modulon.

Laskin myös tuon oman esimerkin. Siinä determinantit olivat 0,0,0,-3 ja -3 eli positiivinen ykkönen tuli oikeaan kohtaan vastaukseksi (nelosnappia painetaan).

Näyttäisi ettei toimi, jos on useita ratkaisuja. Silloin tulee determinanteiksi nollat.

Tuolla on samantapainen ongelma ratkaistu. Siinä tosin on vain yksi ratkaisu ja determinanteilla tavallisella tavalla laskienkin onnistuu (D=-3 Dy=-3, muut 0)

Alkuperäistä tehtävää mukaillen:
Esim. jos on kolme lamppua ja vaikutusalue on yksi kumpaanki suuntaan eli oikeastaan vaikutusalue on 3 ja alkutilassa kaikki lamput palavat -> on kolme vastausta (x,y,z) (1,0,0), (0,1,0) ja (0,0,1) eli käytetään mitä tahansa yhtä kytkintä.

Mitä matemaatikot sanoo?

Eri tehtävien determinantit

B 6/1 det = 0 neljä ratkaisua

C 10/2 det = 0 kuusitoista ratkaisua

D 20/1 det = -3

E 30/7 det=0

F 39/6 det=0

G 53/19 det=19

H 120/7 det=0

I 220/27 det=0

J 500/87 det=0

K 1002/83 det=0

L 2107/108 det=0
Eli noista voi ratkaista determinanteilla suoraan tehtävät D ja G
D ratkaisu 2,5,7,10,11,12,16,19 G ratkaisu 3,7,9,10,11,12,13,16,18,22,24,27,28,29,31,32,33,37,39,40,44,49,50,51,53 (kytkinten numerot)

tehtävä B 6/1 neljä ratkaisua (kytkimien painallukset, kytkin 1,2,3,4,5,6)

1 0 1 0 0 0
0 1 1 1 1 0
0 0 0 1 0 1
1 1 0 0 1 1
Tuossa pitäisi lukita kaksi kytkintä/muuttujaa, jotta saataisiin yksi ratkaisu

tehtävä C 10/2 kuusitoista ratkaisua
1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 0 1 0 0 0
0 1 0 1 1 0 0 1 0 0
1 0 0 1 1 1 1 1 0 0

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

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

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

Tuossa pitäisi lukita neljä kytkintä/muuttujaa, jotta saataisiin yksi ratkaisu (kerrallaan)

Brute forcella kestää kauan jo tehtävä D jossa miljoona (2^20) vaihtoehtoa (riippuu resursseista;).

Mielenkiintoinen ongelma. Huomasin, että jos tuosta onnistuu kirjoittamaan matriisiyhtälön, missä kerroinmatriisi on A, niin ainakin matriisin kääntäminen modulo 2 on pala kakkua Sagelle:

Matrix(IntegerModRing(2), A).inverse()

Tämä osoitteesta http://stackoverflow.com/questions/4287721/easiest-way-to-perform-modular-matrix-inversion-with-python