0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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