0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Sorry edited 52 cards middle 1s section has 26 cards $\endgroup$ – Apoorv Jain May 21 at 16:13
  • $\begingroup$ Have you tried it with a deck of cards? $\endgroup$ – saulspatz May 21 at 16:21
2
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh that was great. I think I should have wrote the states for larger card decks. So what I got is that the invariant property is that it will remain a palindrome. In addition I am able to prove the invariant property as well for transition states. Thanks a lot ! $\endgroup$ – Apoorv Jain May 21 at 17:00
  • $\begingroup$ @ApoorvJain: You’re welcome! $\endgroup$ – Brian M. Scott May 21 at 17:01

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