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.
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
extension of the problem
