4
$\begingroup$

Okay, you have N switches. They are all off. You may flip one switch at a time. You must visit each possible state of switches being flipped without repeating any state. At the end, you must be able to return to the original all-off state with one more flip. How many ways are there to do this? (Bonus: Ignoring the final rule that you must be able to return to the original state in one flip, how many additional ways are there to visit all states?)

Examples:

For 2 switches, this is trivial:

  00
10  01
  11

You can go around the circle in either direction, for a total of 2 possible paths. There is no way to ignore the final rule with 2 switches.

For 3 switches, there are more possibilities:

    000          000          000          000          000          000
 100   001    010   001    100   010    001   010    010   100    001   100
101     011  011     101  110     011  011     110  110     101  101     110
 111   010    111   100    111   001    111   100    111   001    111   010
    110          110          101          101          011          011

You can go around any circle in either direction, for a total of 12. Additionally, you can do any of the following:

000 001 011 010 110 100 101 111
000 001 101 100 110 010 011 111
000 010 011 001 101 100 110 111
000 010 110 100 101 001 011 111
000 100 101 001 011 010 110 111
000 100 110 010 011 001 101 111

These 6 paths will visit every possible state, but end on 111, so they cannot be done in a cycle, since it will take 3 flips to get back to 000.

It can be proven that there are no other paths which visit all states without repeats. Since there are 8 possible states, it will take 7 flips to get to them all, which is an odd number, so there must be an odd number of 1's at the end of the sequence. These 6 circles and 6 straight sequences have exhausted all possible paths that do not repeat.

The question is: How many such cycles exist for N switches? I found these by hand, but there must be some formula that would account for all possibilities in a less tedious manner. (And does this sequence exist in the OEIS? It probably should.)

$\endgroup$
3
  • 1
    $\begingroup$ If you take the different states as a collection of vertices, and join two of them if they differ in one place (i.e. you can move from one to another via a flip). Then your problem turns into one about counting Hamiltonian paths. There may be some work on this. $\endgroup$ – James Sep 7 '15 at 14:33
  • $\begingroup$ If you consider each state as the binary representation of a number from $0$ to $2^n-1$, you can perform a single-flip switch from $p$ to $q$ whenever the difference between $p$ and $q$ is a power of $2$ up to $2^{n-2}$ $\endgroup$ – David Quinn Sep 7 '15 at 15:01
  • $\begingroup$ @James Indeed, the 8 different states for N=3 can be represented as the corners of a cube, and each edge is one flip. For N=2, it's just a square, but for larger N's, you're getting into hypercube higher dimensional stuff. $\endgroup$ – Darrel Hoffman Sep 7 '15 at 15:09
1
$\begingroup$

The number of Hamiltonian cycles in the $n$-dimensional cube is A003042 in OEIS. The number of Hamiltonian paths is A091299.

Edit:

The number of Hamiltonian paths starting from a fixed point (e.g. all off) is A003043.

$\endgroup$
1
  • $\begingroup$ This is at least half of the answer. The first sequence does appear to match my results, but the second is not quite right. I think that is what you get if you can start from any state, not just the all-off state. So possibly it would be A091299 divided by $2^N$? Edit: Which exists at A003043, so there we go. $\endgroup$ – Darrel Hoffman Sep 8 '15 at 13:30
0
$\begingroup$

What you’ve described is known as a “Gray code,” which have been studied fairly extensively. I don’t have a complete answer to your question, but Liposvski in Introduction to Microcontrollers offers the following:

There are a large number of Gray codes. Suppose $G(i)$ is a function that outputs the Gray code of a binary number $i$. Then for an $n$-bit code, for any $j$, $G((i+j)\mod 2n)$ is also an $n$-bit Gray code of $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.