All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Lights Out! (2) (Posted on 2022-10-31)
Imagine there is a 7x7 grid of lights, and only the middle in the grid is on.

The lights are wired such that when you flip the switch for one light (from on to off or off to on) the others next to it (not diagonally) flip as well.

Using this weird wiring of lights, what is the fewest number of switch changes it takes to turn all the lights off, and which lights should you switch?

Note: Assume all the switches work in the manner explained, and there is one switch for each of the lights.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 extension of the problem | Comment 4 of 24 |

I explored this problem a little further.

Mathematically it is a discrete 2-d convolution of a central dirichlet delta function against a function that is the sum of a set of such functions offset.

The convolution must in turn produce a set of delta functions each with an even integer coefficient, except the centermost, which must have an odd coefficient. Here "even" corresponds to turning a light on and off an even number of times so it remains off, while the central cell is turned off and on an odd number of times, leaving it "off" as well. But knowing the framework has not yielded an inversion method, so I settled for more simulations. By requiring 4-fold symmetry (including diagonal symmetry) I reduced the number of trials by a factor of 2^4 = 16

I tried different size grids (sides of 3, 5, 7, 9, 11, and 13) always with only the center cell lit. In this range, solutions exist only for the 3, 7 and 13 square grids, with the "push" given patterns below.

I repeated the experiment for a 3x3 diagonal cross (X) rather than the

up-down, right-left cross (+) of the problem. Again, only grids 3, 7, and 13 had solutions.

For the original (+), the solutions for the 3, 7, 13 sided grids had 5, 17, and 65 pixels on, while the cross solution, for squares of 3, 7, and 13, had patterns containing 5, 17, and 41 points (pushes) respectively.

There was no search for the minimum set of pushes because only one solution existed in each case. The program is here with the results below:

lord@rabbit 12768 % one

Success! side =  3

push cnt=5

o 1 o

1 1 1

o 1 o

side=3 bits=3 cnt=8

side=5 bits=6 cnt=64

Success! side =  7

push cnt=17

o o o 1 o o o

o o 1 1 1 o o

o 1 o o o 1 o

1 1 o 1 o 1 1

o 1 o o o 1 o

o o 1 1 1 o o

o o o 1 o o o

side=7 bits=10 cnt=1024

side=9 bits=15 cnt=32768

side=11 bits=21 cnt=2097152

Success! side = 13

push cnt=65

o 1 1 1 o 1 1 1 o 1 1 1 o

1 o 1 o o o 1 o o o 1 o 1

1 1 o o o o o o o o o 1 1

1 o o o o o 1 o o o o o 1

o o o o o 1 1 1 o o o o o

1 o o o 1 o o o 1 o o o 1

1 1 o 1 1 o 1 o 1 1 o 1 1

1 o o o 1 o o o 1 o o o 1

o o o o o 1 1 1 o o o o o

1 o o o o o 1 o o o o o 1

1 1 o o o o o o o o o 1 1

1 o 1 o o o 1 o o o 1 o 1

o 1 1 1 o 1 1 1 o 1 1 1 o

(Here are the cross cases. Note, again, the 3x3 solution replicates the kernel)

lord@rabbit 12768 % cross

push cnt=5

1 o 1

o 1 o

1 o 1

side=3 bits=3 cnt=8

side=5 bits=6 cnt=64

Success! side =  7

push cnt=17

1 o 1 o 1 o 1

o 1 o o o 1 o

1 o o o o o 1

o o o 1 o o o

1 o o o o o 1

o 1 o o o 1 o

1 o 1 o 1 o 1

side=7 bits=10 cnt=1024

side=9 bits=15 cnt=32768

side=11 bits=21 cnt=2097152

Success! side = 13

push cnt=41

1 o o o o o o o o o o o 1

o 1 o 1 o 1 o 1 o 1 o 1 o

o o o o 1 o o o 1 o o o o

o 1 o 1 o o o o o 1 o 1 o

o o 1 o 1 o o o 1 o 1 o o

o 1 o o o o o o o o o 1 o

o o o o o o 1 o o o o o o

o 1 o o o o o o o o o 1 o

o o 1 o 1 o o o 1 o 1 o o

o 1 o 1 o o o o o 1 o 1 o

o o o o 1 o o o 1 o o o o

o 1 o 1 o 1 o 1 o 1 o 1 o

1 o o o o o o o o o o o 1

side=13 bits=28 cnt=268435456

Edited on November 11, 2022, 9:18 am
 Posted by Steven Lord on 2022-11-11 04:34:13

 Search: Search body:
Forums (0)