Lampor i planet

Hej PA!

Här är ett intressant problem:

Tänk dig ett oändligt rutnät där varje ruta innehåller en glödlampa, som antingen kan vara släckt eller tänd. Ursprungligen är alla lampor släckta. I ett drag får man välja antingen en $3 \times 3$ - eller en $4 \times 4$ -kvadrat och ändra statusen på varje lampa i den kvadraten – släckta lampor tänds, och tända lampor släcks.

Nu till frågan: Är det möjligt att, genom en följd av sådana drag, få exakt fyra tända lampor som bildar en $2 \times 2$ -kvadrat?

Följande är ett exempel på en sådan sekvens av drag – kanske inte den mest effektiva, men ett försök att vara illustrativ. De gula rutorna betecknar tända lampor, och de vita släckta. Den röda kvadraten visar vilken $3 \times 3$ - eller $4 \times 4$ -kvadrat som har valts.

Jag ställer mig tveksam till detta, men det kan bero på att jag inte hittar någon vettig taktik. Problemet jag ser är att då jag försöker släcka några lampor som kommit på lite avvägar tvingas jag samtidigt tända några nya lampor som är lika mycket på avvägar som de som jag släckte.

Här är en helt ekvivalent fråga, som kanske är enklare att besvara (eller hitta en taktik att få släckt/identifiera att det inte går att lösa):

På ett oändligt rutnät är en 2x2-kvadrat upplyst, alla andra lampor är släckta. Kan du hitta en serie med drag som gör att samtliga lampor släcks?

Hej!

Här kommer en liten ledtråd till problemet:

Visa spoiler

Låt oss i första hand titta på ett annat problem:

Antag vi tar ett vanligt $8 \times 8$ -schackbräde och avlägsnar två diagonallt stående hörn. Är det möjligt att fylla det återstående brädet med dominobrickor ( $1 \times 2$ )?

Svaret på frågan är nej. Ett normalt schackbräde innehåller $32$ svarta och $32$ vita rutor. Två diagonalt motstående rutor har alltid samma färg på ett schackbräde, vilket betyder att det stympade schackbrädet innehåller antingen $30$ svarta och $32$ vita, eller $32$ svarta och $30$ vita.

Oavsett hur vi placerar en dominobricka på ett schackbärde kommer den alltid täcka exakt en svart ruta och exakt en vit ruta. För att kunna täcka hela brädet med dominobrickor skulle det därför behöva finnas lika många svarta som vita rutor, vilket inte är fallet här. Därför är det omöjligt.

Nyckeln till lösningen låg i en användbar princip: färgläggning (eng. colouring argument). Samma idé kan tillämpas för att lösa det ursprungliga problemet!

Hej igen!

Här kommer en ny ledtråd som bygger på den förra:

Visa spoiler

Oavsett vilken strategi man försöker kan det vid första anblick verka omöjligt att nå en $2 \times 2$ -kvadrat, precis som Bedinsis påpekade.

I själva verket vill vi visa att det inte går!

Nyckeln ligger, som sagt, i en smart färläggning av planet. Testa att färglägga det i följande mönster av vita och grå rutor:

Låt $S$ vara antalet tända lampor som är belägna på en grå ruta. Vad kan sägas om $S$ efter varje drag?

Svara

Visa senaste svar