Binary Sequence of Single Bit Transitions

Question

First of all, I'll have to say that I believe this problem has no solution, but I'm unable to prove it. Here is the problem: I need an algorithm to generate a sequence of all possible transitions of a N-bits number without repeating elements.

Example: suppose that I have a 3 bit number.
000 -> 001 is a valid transition (1 bit changed)
000 -> 011 is not (2 bits changed)

I could start from a Gray Code sequence (000, 001, 011, 010, 110, 111, 101, 100) but that doesn't cover all possible transitions. See, it doesn't contain 000->010, for example. I wasted some time on it and it feels like there can't be a solution, but how do I demonstrate it? Or how do I solve it?

Answer 1

So, I've been thinking a little more about this and I verified that my problem can be modeled as an Euler circuit finding for directed graphs, and since all my vertices have the same amount of in and out edges the path exists.

Answer 2

There are $2^n$ possible $n$-bit bitstrings, and $n \cdot 2^n$ possible single-bit transitions between them. (Starting from each bitstring, you can flip any of the $n$ bits to obtain a distinct transition.)

Thus, a sequence containing each of the transitions must contain at least $n \cdot 2^n$ elements (actually, $n \cdot 2^n + 1$, if we count the first and the last element separately). Thus, by the pigeonhole principle, for $n > 1$ (and also for $n = 1$, if we're not allowed to loop back to the initial element) the sequence must contain at least one element more than once.