This question is still active as the answer from @Sleafar has just arrived. Not yet solved.
Scenario
The heads of 3 top terrorist organisations are planning to play an extremely high-stake poker game that could potentially decide their respective fates. One of them is Arnab, whose life depends on his winning. He also knows that he is not that good a player, and will have to use illegitimate tactics to win.
He has paid the casino dealer a vast amount of money, in return for him following the certain rules:
- Every new deck (standard 52 card deck) that is requested will be already in order - 4 aces, 4 kings, 4 queens, ... 4 twos.
- He will use customized shuffling algorithms that will ensure there is no pair in the deck. No 2 adjacent cards will be of the same number.
Arnab can, therefore bet large amounts on high cards and other relatively bad hands, and his opponents would fold, thinking that pairs, 3 of a kind, etc. are likely.
Twist
However, on the match day, after just a few hands, his adversaries are quite sure that the casino has been rigged. It becomes more suspicious when they realise that the dealer uses quite fixed algorithms for shuffling.
They have a huge row when they ask the dealer to shuffle randomly, but the dealer refuses. Afraid that they would not be able to find another man who will act as a fair judge/dealer, they agree to a compromise:
- A new deck will be requested for every hand.
- The dealer will use the same algorithm, every time.
- The players will ask him to repeat the same shuffling algorithm a random number of times, before dealing.
- They will also split the deck (at a random card) and deal it, not from the top card.
However, none of them know that the new decks are still ordered - neither the 3 players, nor the dealer. What shuffling algorithm must the dealer use to help Arnab? For how long will it work? Note that Arnab has not communicated with the dealer, and will be unaware of any change in plans.
Formal question
Devise a static shuffling algorithm, such that there are no 2 adjacent cards in the deck. The condition should remain true even after $n$ iterations of the shuffle (on the same deck). Maximize $n$.
Restrictions
- There can be no random choices.
- It can not have conditional statements pertaining to the exact cards. So, a statement like swap cards, if there is an ace is not allowed.
So, a possible shuffle for 4 cards could be written as:
1 2 3 4
$\rightarrow$ 4 2 1 3
It should be possible to write down your shuffle in such a format.
What is the maximum value of $n$ for which this works? ($n$ has to be less than 52)