# shuffling cards

I have $N$ cards with numbers written on it (from 1 to N, each card have only one number). Now, I divide them into $2$ halves. Next, I take one card from second half, one from first half and again, till no cards left. For example: Before shuffling: $1 2 3 4 5 6 7 8$ First half:$1 2 3 4$ Second half:$5 6 7 8$ After shuffling: $5 1 6 2 7 3 8 4$

I repeat shuffling M times. Now, someone is asking me to show him card with number K written on it. But I can't see the numbers, because the cards are faced down. How to tell on which position is card with number K written on it (for $N = 8$, $M = 1$ and $K = 3$ the answer is 6, because after 1 shuffle, card with number 3 is on 6th position)?

I need a mathematical formula for this, because $N, M, K$ can be very large. If $N = 2n+1$, then first half contains $n$ cards and the second half contains $n+1$ cards.

## 1 Answer

Let us first study the case $N = 2n$ is even.

Let us label the slots where the cards can go from front to back as $1$ to $N$.

Define numbers $a(i), 1 \le i \le N$ such that after one shuffling, the card at slot $i$ is moved to slot $a(i)$. When $N$ is even, it is easy to see

$$a(i) = \begin{cases} 2i,& 1 \le i \le n\\ 2i - (N+1),& n+1 \le i \le 2n \end{cases}$$ This can be conveniently represented as $$a(i) \equiv 2 i \pmod {N+1}.$$ Please note that $a(1), a(2), \ldots, a(N)$ is a permutation of $1, 2,\ldots,N$. After $M$ shuffling, the card $K$ will be moved to position

$$k = \underbrace{a(a(a(}_{M\,\text{times}}\ldots(K))) \equiv 2^M K \pmod {N+1}$$

Notice $2(n+1) = N + 2 \equiv 1 \pmod {N+1}$. For the inverse problem, if you are given a slot $k$, the card $K$ occupying it will be given by

$$K \equiv (2(n+1))^M K = (n+1)^M 2^M K \equiv (n+1)^M k \pmod {2n+1}$$

When $N = 2n+1$ is odd, we are told the first half contains $n$ while the second half contains $n+1$ cards. It is easy to see the card at last slot always stay at last slot. The analysis is essentially the same as the even $N$ case. We have $$k = 2^M K \pmod{2n+1}\quad\iff\quad K = (n+1)^M k \pmod {2n+1}$$ for $1 \le k, K \le 2n$ and $k = 2n+1$ when $K = 2n+1$.

• I meant - How to tell on which position is card with number K written on it? So what's the formula for it? – user4201961 Jan 3 '15 at 14:40
• I modify the answer to match what you ask. the card $K$ will be moved to slot $k = 2^M K\pmod{2n+1}$. – achille hui Jan 3 '15 at 14:52