The Modified Faro shuffle.

Question

I came across this problem in George Andrews's book "Number Theory" (section 4-3, problem 2). It deals with a modified version of the Faro shuffle that behaves as such:

$$(1,2,3,4,5,6,7,8) \rightarrow (4,5,3,6,2,7,1,8)$$

Essentially you cut the deck in half, flip the top half ($1,2,3,4$ in our example), and then shuffle them back together ensuring that the bottom card (8) stays at the bottom. The question asks us to prove that a deck with $2^n$ cards will return to it's original state after $n + 1$ shuffles.

The book implies that this is solved using congruence relations but I haven't been able to come up with anything substantial. I see that the piece-wise function

$$f1(x) = -2x \mod(2^{n} + 1)\quad \text{for}\quad \{x: 1 \le x \le 2^{n-1}\}$$

and

$$f2(x) = 2x + 1 \mod(2^{n} + 1) \quad \text{for}\quad \{x: 2^{n-1} \lt x \le 2^{n}\}$$

correctly map the elements but repeated composition of this function hasn't gotten me anywhere. (These two pieces can be combined into one function using an absolute value operator but composition is just as ugly) Any hints or insights you can provide would be appreciated.

Answer 1

Something which may (or may not help) : You can represent these operations with permutation matrices, for the example where the deck is 8 (for simplicity to read whitespace means zeros):

$${\bf P}_{fliptop} =\left[\begin{array}{cccccccc} & & &1& & & & \\ & &1& & & & & \\ &1& & & & & & \\1& & & & & & & \\ & & & &1& & & \\& & & & &1& & \\ & & & & & &1& \\ & & & & & & &1\end{array}\right], {\bf P}_{shuffle} = \left[\begin{array}{cccccccc}1& & & & & & & \\ & & & &1& & & \\ &1& & & & & & \\ & & & & &1& & \\ & &1& & & & & \\ & & & & & &1& \\ & & &1& & & & \\ & & & & & & &1\end{array}\right]$$ Now if we do ${\bf P}_{shuffle}{\bf P}_{fliptop}$ on our column vector:

$${\bf P}_{shuffle}{\bf P}_{fliptop}[1,2,3,4,5,6,7,8]^T = [4,5,3,6,2,7,1,8]$$

Which is as in the question. Now the combined operation is just the matrix product between the matrices above.

Answer 2

Let the cards be numbered 0 to (2^n)-1 from to top bottom We will ignore the last card as it always remains at the bottom. The shuffle for the all other cards except the last one can be represented as

-2x-1 mod (2^n)-1 for 0 <= x < (2^(n-1)) -1 2x mod (2^n)-1 for (2^(n-1)) <= x < (2^n) -1 where x represents position of card

We can represent x in terms of t as follows:

x = t1 when 0 <= x < (2^(n-1)) -1 where 0 <= t1 <= (2^(n-1))-1 x = (2^(n-1)) + t2 when (2^(n-1)) <= x < (2^n)-1 where 0 <= t2 <= (2^(n-1))-2

The shuffle can now be represented as

-2x-1 mod (2^n)-1 = (2^n) -1 -2t1-1 = (2^n) -2t1 - 2 when 0 <= x < (2^(n-1)) -1 2x mod (2^n) - 1 = (2^n) + 2t2 mod (2^n) - 1 = 2t2 + 1 when (2^(n-1)) <= x < (2^n)-1

We will transform x to y where y = 4x+2 mod (2^(n+1)) -1 The transformation from x to y is unique, i.e. for every x there is a distinct y as seen below y = 4x+2 mod (2^(n+1))-1 = 4t1 + 2 when 0 <= x < (2^(n-1)) -1 y = 4x+2 mod (2^(n+1))-1 = 4*(2^(n-1) + 4t2 + 2 mod (2^(n+1))-1 = 4t2 + 3 when (2^(n-1)) <= x < (2^n)-1 4t1+2 covers all numbers of that form between [0, (2^(n+1))-2] as 0 <= t1 <= (2^(n-1))-1 4t2+3 covers all numbers of that form between [0, (2^(n+1))-2] as 0 <= t2 <= (2^(n-1))-2 Thus the numbers 0 to (2^(n)) -2 in the original deck are transformed to distinct numbers in mod (2^(n+1)) -1

Let us see what the shuffle is in terms of y

When x = t1, y = 4t1+2, After shuffle x becomes (2^n) -1 -2t1 -1 = (2^n) -2t1 - 2, y becomes 4((2^n) -2t1 - 2)+2 mod (2^(n+1))-1 = (2 -8t1 - 8) + 2 mod (2^(n+1))-1 = -8t1 -4 mod (2^(n+1))-1 = -2y mod (2^(n+1))-1 Since every number x from 0 to 2^(n)-2 becomes transformed to number of the form 4t1+2 or 4t2+3 in the mapping to mod2^(n+1)-1,-2y must also be a number of the form 4t1+2 or 4t2+3 as it also come from a transformation.

When x = (2^(n-1)) + t2, y = 4t2 + 3 After shuffle x becomes 2t2 + 1, y becomes 8t2 + 6 mod (2^(n+1))-1 = 2y mod (2^(n+1))-1 2y will also be form 4t1+2 or 4t2+3 as it also come from a transformation.

Thus a card at position x when shuffled, its transformation y = 4x+2mod (2^(n+1)) - 1 becomes -2y when 0 <= x < (2^(n-1)) -1 2y when 2^(n-1)) <= x < (2^n) -1

x after n+1 shuffles in the transformation becomes either (2^(n+1))y or -(2^(n+1))y mod (2^(n+1)) - 1 Now (2^(n+1))y mod (2^(n+1)) - 1 = y and -(2^(n+1))y mod (2^(n+1)) - 1 = -y

We will now prove it cannot be -y

(y + -y) without modulus being applied must equal (2^(n+1)) - 1 as y is > 0 There are 3 possibilities

i) Both y and -y are of the form 4t1+1 Say y = 4p1+2, -y = 4p2+2 where p1, p2 are variables in the same range as t But the above sum is even but (2^(n+1)) - 1 is odd, so this not possible

ii) Both y and -y are of the form 4t2+3 Again their sum is even, so this is not possible

iii) If y is of the form 4t1+2, -y is of the form 4t2+3 or vice-versa Their sum is of the form 4s+1, (2^(n+1)) - 1 is of the form 4s+3, so this is not possible

Thus after n+1 shuffles, y becomes y , i.e x becomes x as the transformation is one to one.