The “Circlular Spatula” Puzzle

Problem

Try out the puzzle here (with parameters $(8, 3)$ ), and view the source code here.

It's a variant of the Google Code Jam “oversized spatula” puzzle. The goal of the puzzle is to turn on all $n$ lights. You can press a light, which toggles the $k$ neighboring lights.

You can consider the puzzle with parameters $(n, k)$ , where $n$ is the number of lights and clicking toggles $k$ lights at a time

I wasn’t able to find any other analysis. Maybe this is also a famous puzzle which has already been solved; in which case, I'm re-inventing the wheel.

Solution

The solution when $k$ is odd is just to click all the lights once.

It works because all the actions commute. This is easy to see, since if you click two lights in a different order, the number of toggles for each light will be the same. So since $k$ is odd, each light will be toggled $k$ times and end up in the on state.

Minimality

The main question this post asks is, given parameters $(n, k)$ , does the solution described above use the minimal number of steps? (This question was asked by a friend I showed this to.)

Computational Approach

It's easy to see that the solution above is minimal if $k = 1$ (the only way to enable all the lights is to click each one). Since $k = 1$ , all $2^n$ possible states are reachable. If all states are reachable, then each state has a unique set of clicks that results in it. So, if all states are reachable, there is only one solution (and it is therefore minimal).

Which $(n, k)$ does the puzzle have the same number of reachable states as the puzzle does for $(n, 1)$ ?

from itertools import product
from fractions import gcd

def flipK(arr, i, k):
    l = len(arr)
    for j in xrange(i, i+k): arr[j%l] += 1

def express(arr, k):
    """ returns expression of the action [arr] in the puzzle """
    out = [0 for _ in xrange(len(arr))]
    for i, a in enumerate(arr):
        if a: flipK(out, i, k)
    return tuple([o % 2 for o in out])

def is_same(n, k):
    expressions = [express(action, k) for action in product([0, 1], repeat=n)]
    num_total = len(expressions) # states for (n, 1)
    num_uniq = len(set(expressions)) # states for (n, k)
    return num_total == num_uniq

solutions = []
for n in xrange(2, 18):
    for k in xrange(1, n+1, 2):
        if is_same(n, k):
            solutions.append((n, k))

print solutions

"""
Output (n, k):
[(2, 1), (3, 1), (4, 1), (4, 3), (5, 1), (5, 3), (6, 1), (6, 5), (7, 1), (7, 3), (7, 5), (8, 1), (8, 3), (8, 5), (8, 7), (9, 1), (9, 5), (9, 7), (10, 1), (10, 3), (10, 7), (10, 9), (11, 1), (11, 3), (11, 5), (11, 7), (11, 9), (12, 1), (12, 5), (12, 7), (12, 11), (13, 1), (13, 3), (13, 5), (13, 7), (13, 9), (13, 11), (14, 1), (14, 3), (14, 5), (14, 9), (14, 11), (14, 13), (15, 1), (15, 7), (15, 11), (15, 13), (16, 1), (16, 3), (16, 5), (16, 7), (16, 9), (16, 11), (16, 13), (16, 15), (17, 1), (17, 3), (17, 5), (17, 7), (17, 9), (17, 11), (17, 13), (17, 15)]
"""

We can see by inspection that for $n \le 17$ , the result is true when $k$ is odd and $(n, k) = 1$ , where $(\cdot, \cdot)$ represents $\mathrm{gcd}(\cdot, \cdot)$ .

We'll now show that this is true in general if $k$ is odd and $(n, k) = 1$ . In other words, when $(2n, k) = 1$ .

Analysis

Claim

For parameters $(n, k)$ where $(2n, k) = 1$ , the action of clicking all the buttons (which we'll call $(1, 1, ..., 1)$ ) is the unique solution.

Notation

We'll use $n$ -tuples $A = (1, 0, 1, ...)$ to represent actions (i.e., the action $A$ of clicking the first, third, etc. lights in any order). Multiple actions can be composed by writing $A = A_1 A_2$ .

We'll define the "simple" action $I_j = (0, ..., 0, 1, 0, ... 0)$ . In other words, $I_j$ is the action of clicking the $j$ th light.

We'll use $S = (A)_{(n, k)}$ to denote the state resulting from applying the action $A$ to the all-off state, under the parameters $(n, k)$ .

And we'll let $P(n, k)$ be the set of possible states in the puzzle with parameters $(n, k)$ .

If we prove the following equivalent claim, then the claim follows from the counting argument mentioned above.

Equivalent Claim

If $(2n, k) = 1$ , then $P(n, k) = P(n, 1)$ .

Proof

We’re going to flip exactly one light (that is, explicitly construct the state $(I_x)_{(n, 1)}$ ) using actions on $P(n, k)$ .

We'll do this by flipping adjacent ranges of lights until we get one light. Consider the state $(I_0 I_k I_{2k} ... I_{l \cdot k})_{(n, k)}$ and consider $0, k, 2k, ..., l \cdot k$ as a sequence in $\mathbb{Z}_{2n}$ .

Notice that for any $j \cdot k \in \mathbb{Z}_{2n}$ , then $n - |(j \cdot k \mod 2n) - n|$ is the number of lights in the enabled state.

Therefore, the end state has only one light flipped if and only if $l \cdot k \in \{1, -1\}$ .

The key insight is that since $(2n, k) = 1$ , then $k$ is a generator for $\mathbb{Z}_{2n}$ , and there is always some $l$ where $l \cdot k \in \{1, -1\}$ .

So, for this value of $l$ , we have $(I_0 I_k I_{2k} ... I_{lk})_{(n, k)} = (I_m)_{(n, 1)}$ . Notice that we can shift this action clockwise by any amount, and construct the state $(I_x)_{(n, 1)}$ .

Since we have constructed the action of pressing every button under $P(n, 1)$ , and we can compose these "simple" actions, then by closure we can conclude that $P(n, 1) \subset P(n, k)$ .

Also, every state in $P(n, k)$ can be constructed in $P(n, 1)$ by simply clicking the lights that are active in the state from $P(n, k)$ . Therefore, $P(n, k) = P(n, 1)$ .

demo — We have essentally shown that every path contains a "1" state, and that we can rotate and compose these "1" states to produce any possible state.

Additional Comments

For some $(n, k)$ , the puzzle is actually not solvable – for example, $(3, 2)$ . I wasn’t able to work out in general when the puzzle is solvable if $(2n, k) \neq 1$ , but I would be interested in playing around with this in the future.