# Exhaustive path through 2^n bit configurations

There's a little play by Samuel Beckett called 'Quad' that consists of nothing else than 4 characters walking on and off stage, one at a time. No two actors leave/enter simultaneously, so only one such change happens at any one time. In the course of the play, every possible combination of actors is on stage (16 distinct configurations).

Here is the play in binary, with each actor represented by their own digit (1 means onstage, 0 means offstage): 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

There is no reason why the 16 values need to appear in this order. For each number there are four others that could be visited, e.g. 1011 -> 0011, 1111, 1001, or 1010

(1) If we always begin with an empty stage, how many different 'paths' can be taken through the 16 configurations? (2) Is it possible to start such a path and end up at a 'dead end', e.g., a situation where you attain 1011 but all of 0011, 1111, 1001, and 1010 have already been visited? (3) How can this be generalized for n actors?

I know this is a solved problem, and probably pretty trivial, but I don't know where to begin researching it.

• This is related to the problem of finding De Brujin Sequences. You could solve this in a similar fashion by describing it using a graph with vertices as possible play-states, edges as possible progressions from one state to another, and calculating how many Hamiltonian Paths exist for the graph. – JMoravitz Feb 23 '16 at 17:00
• It's also something like a Knight's Tour, except on a board without edges. – pgblu Feb 23 '16 at 17:09
• I have since found the following reference: cis.uoguelph.ca/~sawada/papers/beckett_endm.pdf This is classified as a 'hard problem' so I feel better (for not having figured it out) and worse (for having assumed that it is trivial) – pgblu Feb 23 '16 at 18:31
• are "cycles" allowed ? – Abr001am Feb 23 '16 at 19:24
• Cycles are allowed. – pgblu Feb 25 '16 at 16:01