The below problem has been taken from Mathematics for Computer Science (MIT Opencourseware https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/readings/MIT6_042JS15_textbook.pdf Problem 5.35)
Suppose that you have a regular deck of cards arranged as follows, from top to
bottom:
0000000000000111111111111111111111111110000000000000
Note I have represented only whether card is black or not. 0 representing white, 1 otherwise.
Only two operations on the deck are allowed: inshuffling and outshuffling. In
both, you begin by cutting the deck exactly in half, taking the top half into your
right hand and the bottom into your left. Then you shuffle the two halves together
so that the cards are perfectly interlaced; that is, the shuffled deck consists of one
card from the left, one from the right, one from the left, one from the right, etc. The
top card in the shuffled deck comes from the right hand in an outshuffle and from
the left hand in an inshuffle
I have tried observing the invariant condition here and writing a few state transitions however I haven't been able to identify any useful property. Could you all suggest something ?
HINT:
With $4$ cards: from $0110$ you can reach $10\color{red}{01}$ and $01\color{red}{10}$.
With $8$ cards: from $00111100$ you can reach $0101\color{red}{1010}$, $1010\color{red}{0101}$, $0110\color{red}{0110}$, $1001\color{red}{1001}$, $0011\color{red}{1100}$, and $1100\color{red}{0011}$.