Is every arrangement reachable by shuffling this way?

Question

Suppose we have a vertical stack of $n$ distinguishable coins, each of which is either heads-up or tails-up. Let a shuffle be the following procedure: divide the stack at will into a top- and bottom-stack, and simply rotate the entire top stack $180^\circ$ as a unit. Thus, for $1\le k\le n$:

$$\underbrace{x_1,...,x_{k}}_{\text{top stack}},\underbrace{x_{k+1},...,x_n}_{\text{bottom stack}} \\ \downarrow\\ \overline{x_k},...,\overline{x_{1}}, x_{k+1},...,{x_{n}}$$

where each $x_i$ is either $H_i$ or $T_i$, and

$$\overline{x_i} = \begin{cases} H_i, & \text{if }x_i = T_i \\ T_i, & \text{if }x_i = H_i. \end{cases} $$

Since there are $2^n$ conceivable unsubscripted $H/T$ sequences, and there are $n!$ ways to append the subscripts to each, there are $n! \cdot 2^n$ conceivable ways to arrange the stack.

Is it the case that, for any $n$, all of these conceivable arrangements are reachable by repeated shuffling (no matter what the initial arrangement)?

Answer 1

Yes.

We know that if we can swap any two adjacent items (without any other changes) and do this repeatedly then we can get all permutations. And if we can flip any single coin (without any other changes) and do this repeatedly then we can get all arrangements of heads and tails.

To flip coin $x_n$, first rotate the top $n$ coins, so $x_n$ is now on top. Then rotate only the top coin so it is flipped, then rotate the top $n$ coins. $x_n$ will then be in its original place, flipped, while no other coin is changed.

To swap two adjacent coins, rotate from the top of the stack to the lower coin, so those two coins are now on top. Then rotate those two coins, so they are both swapped and flipped. Then flip each of those coins, as in the previous paragraph. Then rotate coins again to get those two back to their original position.

Answer 2

Yes, you can get all of them. It suffices to show that you can get any desired coin to the bottom in either orientation, since you can then manipulate the rest of the stack without affecting the bottom coin and so build the desired sequence from the bottom up. But this is easy: any coin can be brought to the top in at most one move, where it can be flipped if necessary before the stack is inverted to bring it to the bottom.

Answer 3

Asking whether every arrangement can be reached is the same as asking whether every arrangement can be sorted (into a certain given configuration, such as having the subscripts in ascending order and all coins heads-up).

Other posters have pointed out that this is possible. The question of how to this efficiently is known as the "Burnt Pancake Flipping Problem". You (a waiter) have a stack of pancakes of all different sizes, but they're out of order--you want to sort the pancakes in order by size, so the biggest one is on the bottom, followed by the next-biggest, and so on. The only operation available to you is to take a spatula, insert it somewhere into the stack, lift the stack of pancakes above the spatula, invert it, and replace it.

Further, one side of every pancake is burnt, and (for the sake of presentation) you want to put all the burnt sides face-down. (This corresponds to the Heads/Tails in your coin example.)

Various algorithms have been produced to sort a given stack of burnt pancakes, with the goal of using the fewest flips necessary. Further information:

http://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman

http://en.wikipedia.org/wiki/Pancake_sorting#The_burnt_pancake_problem

http://www.math.illinois.edu/~dwest/openp/pancake.html

Why is sorting pancakes NP hard?

http://arxiv.org/pdf/1010.0219v1.pdf

FYI, this problem is related to the study of DNA mutation. Also, you might be interested to know that Bill Gates coauthored a paper on the "unburnt" variation of this problem.