# Putting up the lights

Feeling festive, you decide it's time to put up the lights. You dig out the box and plug a strand in. Uh oh, they are all the same color. This won't work, these are supposed to be multiple colors and broadcast your magnificence of exterior illumination skills! Now you have a hundred strands of 20 lights all the same blue color. Another glance in the box reveals a letter.

Hello future me! This is past you talking...or writing... Anyway, you know how we like puzzles? Well further-past you thought it would be funny to reset all the lights to the same color. I managed to figure it out with help from the manual and decided I should repay the favor. Unfortunately, that manual has been... misplaced. Here's what you need to know, though.

Each strand of 20 lights is wired like a 5x4 grid, and each bulb can be either blue, red, purple, or green. However, when you change the color of 1 bulb, the adjacent ones in the grid will cycle to the next color as well. The good news, though, is that this doesn't seem to wrap around. Good luck future me!

"I really hate you past me", you mutter to yourself as you examine the lights. You change the color of the 1st light and the 2nd and 6th lights also change to red. You change it again, and the same three become purple. Cycle again makes them green, and one last time brought them back to blue. Just to make sure, you cycle through the colors of the 7th light and notice the 2nd, 6th, 8th, and 12th lights follow suit.

"Alright, I can do this", you encourage yourself. You decide you want the lights to alternate the length of the strand (blue, red, purple, green, blue, ...) The problem is, you need a quick strategy to do this so you're not wasting all day doing it for your hundred strands. You grab a pen and paper to write down steps and get to work...

• Is each strand wired the same way? That is, if I change the 1st light on a different strand, it will affect the 2nd and 6th on that one too? – user812786 Dec 28 '16 at 21:27
• @whrrgarbl Each strand is identical and stands alone. So yes, the 1st light on a strand also affects the 2nd and 6th on that strand, but only that strand. No light will affect a light on a different strand. – David Starkey Dec 28 '16 at 21:30
• Are we allowed to use a computer program? – Wen1now Dec 29 '16 at 1:58

I believe it's

0 3 3 1 2
1 3 3 1 1
1 0 1 2 1
0 2 2 0 2

where the answer is expressed like this:

A B C D E
F G H I J
K L M N O
P Q R S T


where A represents the first light, B the second and so on. If a light X is pressed n times then the letter X is n. For example in my solution light 1 is pressed 0 times, light 2 is pressed 3 times, light 12 is not pressed, etc.

Background (Step 1):

So obviously this is a mod 4 question, as the cycles have length four. Furthermore pressing a button four times has no net effect. Also it does not matter which order the buttons are pressed in. Therefore we can reduce this down to an 4x5 array where each number is in the set [0,1,2,3].

Step 2:

Now the top row can be anything, but it fully dictates what the second row is. So we only need to bash out all the cases for the top row. Utilising a computer program (Python) I bashed out all the cases.

• +1 for correctness and creativity. But rather than a brute force solution, is there a mathematical or proof-based approach? – MikeQ Dec 29 '16 at 5:36
• The Lights Out puzzle is basically Linear Algebra (jaapsch.net/puzzles/lomath.htm#linalg). Instead of brute forcing all possibilities for the top row, you can look what effect a single top-row move has on the bottom row if you try to keep the other rows unchanged, and then see what linear combination of top-row moves does what you need. For that you need to solve a set of linear simultaneous equations (mod 4), which can be done by inverting a matrix. – Jaap Scherphuis Dec 29 '16 at 7:43
• BTW, the grid is 4x5 so it is easier to consider a length 4 side to be the top row. This makes for fewer possible states to check than if you used the long side at the top, and if you're doing it by linear algebra, fewer equations or a smaller matrix to invert. – Jaap Scherphuis Dec 29 '16 at 7:48
• @MikeQ Bonus question: given a 4x5 array of integers, is it always possible to find a sequence? Extension – Wen1now Dec 29 '16 at 12:09