Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-05-10 22:06:20

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

The mathematics of Lights Out

You have a square or rectangular grid of lights, some of which are on and some off. If you press any light, you toggle its state and that of any adjacent light to its left, right, top and bottom. (Diagonal neighbours are not affected.) The idea of the puzzle is to turn off all the lights. So?

Well, if a light is on, it must be toggled an odd number of times to be turned off. If a light is off, it must be toggled an even number of times (including not being toggled at all) for it to remain off. A successful operation is therefore a sequence of presses that toggles all the “on” lights an odd number of times and all the “off” lights an even number of times. smile

Two points may be noted:

• The order in which the lights are pressed does not matter. The end result of pressing a given set of lights is always that each light has been toggled a certain number of times. (For example, suppose the lights are numbered #1–#25 left to right from top to bottom. Pressing #3, #8 and #14 will toggle #2, #4, #7, #14, #15, #19 exactly once and #3, #8, #9, #13 exactly twice. No matter in what order you press #3, #8 and #14, all the affected lights will be toggled the same way in the end.)

• Each light needs to be pressed no more than once. Note that pressing a light twice is equivalent to not pressing it at all (indeed pressing a light an even number of times is equivalent to not touching it while pressing it an odd number of times is equivalent to doing so just once). Since the order in which the lights are pressed does not matter, a sequence in which one light is pressed twice is equivalent to the same sequence with those two presses removed. Hence, the most efficient method of solving any puzzle (one that uses the minimum number of moves) is one in which no light is pressed more than once.

Well, that’s my theory. I hope it’s correct, as I’ve actually edited the two Wikipedia articles on Lights Out to contribute this insight of mine! big_smile

http://en.wikipedia.org/wiki/Lights_Out_%28game%29
http://en.wikipedia.org/wiki/Lights_Out_%28puzzle%29

Then again, since anyone can edit wiki pages, it wouldn’t really be a disaster if I am wrong. If my theory is incorrect, someone can always edit it out, and no harm will be done – except to my pride and vanity. tongue

Last edited by JaneFairfax (2007-05-11 11:04:32)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#2 2007-05-11 04:13:22

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: The mathematics of Lights Out

Note that pressing a light twice is equivalent to not pressing it at all (indeed pressing a light an even number of times is equivalent to not touching it while pressing it an odd number of times is equivalent to doing so just once).

I don't think this is so.  Pressing a light, then an adjacent light, then that light again will change the puzzle.  So it is not the equivalent of just pressing it twice in a row.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2007-05-11 05:43:20

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

Okay, let’s see. Suppose we press the light with co-ordinates (m,n). Then we press an adjacent light, say (m+1,n), and then the light (m,n) again.

Pressing (m,n) toggles the following lights: (m,n), (m+1,n), (m,n+1), (m−1,n), (m,n−1)

Pressing (m+1,n) toggles the following lights: (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1)

Finally pressing (m,n) again toggles the same first five lights.

The upshot of all this is that 8 different lights have been toggled. Of these, (m,n+1), (m−1,n) and (m,n−1) have been toggled exactly twice, so there is no change in their state. Of the others, (m,n) and (m+1,n) have been toggled exactly three times while the rest have been toggled exactly once – so these have changed state.

In other words, the lights that have changed state are (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1) – which are precisely those lights that would be toggled by pressing just the adjacent light (m+1,n) alone. smile

Last edited by JaneFairfax (2007-05-11 05:48:41)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#4 2007-05-11 06:53:48

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: The mathematics of Lights Out

I would agree with both of those statements. With that in mind, it's possible to easily optimise some solutions.

The wikipedia page gives a very sloppy way of solving a board.
Basically, eliminate all rows except the bottom one by pressing all lights directly below 'on' lights and working your way downwards. Then look at a table and press buttons according to what lights are left on in that row.

The worst part is that even then you may not be done, and you'd have to repeat the process until you finished. It's very possible that you might take a far higher number of moves that you need to. But to improve it, you'd just write down all the moves of the 'bad' solution, cross out repeating squares in pairs, and there you have a better solution. Possibly still not the best one, but certainly an improvement.

That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?


Why did the vector cross the road?
It wanted to be normal.

Offline

#5 2007-05-11 07:21:26

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: The mathematics of Lights Out

my intution says yes, treating it as a long list of simultaenous equations that have to be satisfied, there are probably most deffinately not a single unique solution


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#6 2007-05-11 11:54:47

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

mathsyperson wrote:

That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?

Yes indeedy, they can. Consider the following setup:

You can do it the short way by pressing the four corner lights. Or you can do it the long way by pressing all the lights on the edge plus the second-from-left, second-from-right, second-from-top and second-from-bottom middle lights. Neither solution involves pressing a light more than once. If you don’t believe it, you can try it yourself here: http://www.guzer.com/games/switchit.php tongue

PS: There is a very interesting corollary to the above. Notice that the short solution is actually contained in the long solution. This means that if the lights are numbered #1–#25 left to right from top to bottom, then pressing the following lights (in any order) will leave the entire board unchanged: #2 #3 #4 #6 #8 #10 #11 #12 #14 #15 #16 #18 #20 #22 #23 #24. (That’s all the even-numbered lights plus the midpoints of the four edges of the grid.)

Last edited by JaneFairfax (2007-05-11 20:47:22)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#7 2007-05-11 20:21:34

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

And after a good night’s sleep, I’ve found another example: big_smile

Short solution: Press #3 #11 #15 #23 (i.e. the midpoints of the edges of the grid)
Long solution: Press all the even-numbered lights

Again neither solution involves pressing a light more than once. This time, however, neither solution is contained in the other! This makes the example wholly non-trivial. tongue

Here’s the proof of why the long solution works. Since the even-numbered lights are all either at least two lights apart or diagonally separated, pressing an even-numbered light has no effect on any even-numbered light other than itself. Of the odd-numbered lights, only the ones at the midpoints of the grid edges are adjacent to an odd number of even-numbered lights. All the other odd-numbered lights are adjacent to an even number of even-numbered lights. Hence pressing all the even-numbered lights will change the state all the even-numbered lights plus #3, #11, #15 and #23, and leave the state of all the other lights unchanged – in other words, it should turn off all the lights above.


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#8 2007-05-11 23:30:06

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: The mathematics of Lights Out

Excellent work! So, as well as crossing out pairs, it's also possible to improve solutions by making a list of sets of buttons that don't affect the board overall and then crossing out any of those that appear. You might not get to use that method as often, but when you do it would improve the solution by a *lot*.

So now that we know that it's possible to have solutions that aren't contained in each other, the next logical question would be whether or not you can have more than one optimal solution. wink


Why did the vector cross the road?
It wanted to be normal.

Offline

#9 2007-05-12 00:20:05

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

Yes, let’s work on it. smile Meanwhile. I believe we can use some mathematical tools to help us in our analysis.

Thus, using this simpler notation, my first board above can be represented by the matrix

and the second board above by

The two statements in my first post can thus be formally stated as theorems. big_smile

Theorem 1:

(NB: I’ve stated the theorem for only two multipliers; mathematical induction should see to it that it works for any finite number of multipliers.)

Theorem 2:


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#10 2007-05-12 00:50:05

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

Theorem 3:

where + is matrix addition. And Theorem 3 proves the other two theorems! Theorem 1 is proved by the fact that matrix addition is commutative and associative, while Theorem 2 is proved by the fact that since the matrices in

are over a two-element field, L + L = 0 for all L
.


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#11 2007-05-12 01:17:07

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

Conjecture:
Let us call the matrix P[sup](m,n)[/sup] in Theorem 3 a “pressing” matrix (as it represents the pressing of a light). Then this conjecture claims that every board setup L is the sum of finitely many pressing matrices.

Pressing matrices would then thus the fundamental building blocks of the game of Lights Out. It would mean that starting with the zero matrix (the board with all lights off), we could arrive at any arbitrary board configuration by executing a finite series of presses – which would mean (working in reverse) that every board setup in Lights Out can be solved.

PS: In the 5×5 case, there are only 25 pressing matrices. Therefore the number of finite combinations of distinct pressing matrices is only finite. It should thus be straightforward to check if between them they yield all the 2[sup]25[/sup] possible board configurations – you just need a good program, or a lot of time on your hand. tongue

Last edited by JaneFairfax (2007-05-12 02:06:00)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#12 2007-05-12 03:27:26

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: The mathematics of Lights Out

Wait a minute. There are 2[sup]25[/sup] board configurations, and there are also 2[sup]25[/sup] non-repeating combinations of buttons.

But in your 2nd example above, you showed that there are distinct non-repeating combinations that change the board in the same way. So then, because the number of configurations is the same as the number of combinations, that must mean that there are some boards that can't be solved. I'd always assumed the opposite.


Why did the vector cross the road?
It wanted to be normal.

Offline

#13 2007-05-12 04:31:00

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

Oops, I didn’t spot that. yikes


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#14 2007-05-12 12:33:31

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: The mathematics of Lights Out

I investigated this a bit further. From the Wikipedia article, every board can be reduced to just one lit line, and then from there you try to do stuff to make the last line go out.

Labelling the last line ABCDE, there are 5 different operations that you can do that affect nothing but the last line. These are BCE, ABC, ABDE, CDE and ACD.

Clearly, all of the board combinations can be reduced to one of the 32 boards that only involve the last line, and from there it's a question of which of those can be solved. Perhaps surprisingly, the only solvable boards other than the ones that are solved by just one of those operations are AE and BD (and of course, the one without any lights).

From there, a bit more poking around reveals that there are 3 sets of unsolvable boards such that each element can be transformed into another element in the set but no other.

Set 1:
{A, ABCE, ABD, ACDE, BC, BDE, CD, E}

Set 2:
{ABCD, ABE, AC, ADE, B, BCDE, CE, D}

Set 3:
{AB, ABCDE, ACE, AD, BCD, BE, C, DE}

Interestingly, each of those sets is just the solvable set but with A, B and C respectively added to each element.

A useful consequence of this is that if you get a randomly generated Lights Out board, then reducing it to one light on the edge of the board is proof that it can't be solved.


Why did the vector cross the road?
It wanted to be normal.

Offline

#15 2007-09-21 03:38:16

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: The mathematics of Lights Out

Bump.

Can some very clever person extend on what we already know and apply it to Lights Out 3D?

I tried briefly, but it seems a lot more complicated.


Why did the vector cross the road?
It wanted to be normal.

Offline

#16 2007-09-21 07:30:56

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: The mathematics of Lights Out

I think the basic concepts are the same, only you work with “3D matrices” instead of 2D matrices. tongue


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

Board footer

Powered by FluxBB