Rigged casino that prevents pairs

Question

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)

Answer 1

Here is a permutation that works upto n=12:

1 6 11 4 5 10 15 8 9 14 19 12 13 18 23 16 17 22 27 20 21 26 31 24 25 30 35 28 29 34 39 32 33 38 43 36 37 42 47 40 41 46 51 44 45 50 3 48 49 2 7 52

Essentially, keep the first and fourth cards with same rank in its place. And permute the second cards of all ranks cyclically, and the third cards of all ranks cyclically with a different shift.

This will ensure no pairs for first 12 shuffles, and the deck returns to its original state after the 13th shuffle.

Perhaps things can be improved by combining the two cyclic permutations somehow. I tried generating random permutations to see how well they work, but none of them seems to do better than n=5.

Answer 2

Solution (n = 16 17)

1, 50, 3, 52, 46, 2, 44, 47, 9, 8, 11, 45, 38, 10, 36, 39, 17, 16, 19, 37, 30, 18, 28, 31, 25, 24, 27, 29, 22, 26, 20, 23, 33, 32, 35, 21, 14, 34, 12, 15, 41, 40, 43, 13, 6, 42, 4, 7, 49, 48, 51, 5

Starting position:

AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMM

17 steps:

AMAMLAKLCBCLJCIJEDEJHEGHGFGHFGEFIHIFDICDKJKDBKABMLMB
ALABKMDACLCBIBFCEJEDGDHEGHGFEFJGIFIHCHLIKDKJAJMKMBML
ABALJLJMCACAHLHLECECFJFJGEGEDHDHIGIGBFBFKIKIMDBDMKMK
AKAKDBIBCMCMFAGBELEBHCEDGJGDJECFIHIFLGAHKFKHLILJMDMJ
ADAJIKHLCBCLGMFAEBELELDCGDGJCJBEIFIHAHMGKHKFBFKIMJMD
AJADFDFKCLCBHBHMEAEAJBJBGCGCLDLDIEIEMFLFKGKGKHJHMIMI
AIAIHJGJCKCKFLELEMEMDACLGBGLBCAJIDIJBEBHKFKHDGDFMHMF
AHAFGIHDCJCDEKJBELEBCMLAGLGBABMCIJIDLDKEKHKFJFIGMFMH
AFAHFHFICDCJDJDKEBELBLBMGAGAMLBLICICKJDJKEKEIHFHMGMG
AGAGHFEFCICIJDCDEKEKLBABGMGMLALBILIBJCJDKJKDHEHFMHMF
AHAFEGDHCFCHCIBJEDEJAKMLGBGLBMKAIBILDLICKDKJFJGEMFMH
AFAHJHJGCHCFLFLIEJEDMDLKGLGBKBJMIAIAIBHBKCKCGDFDMEME
AEAEDFCFCGCGBHAHEIEIBJBJGKGKDLDLIMIMFAFLKBKLHCHJMDMJ
ADAJCELHCFCHAGMFEHEFLIKDGJGDJKIBILIBHMGAKLKBFBECMJMD
AJADBDBECHCFMFBGEFEHKHDIGDGJIJFKIBILGLHMKAKAELJLMCMC
ACACLJAJCECELHLHEGEGJFJFGIGIHDHDIKIKFBFBKMKMDADBMLMB
ALABACMDCJCDBEKFEHEFDGIHGFGHFIGJIDIJHKELKBKLJMCAMBML

First pair in step 18:

ABALMLLCCDCJKJJEEFEHIHHGGHGFGFFIIJIDEDDKKLKBCBBMMAMA

Returns to starting position in step 19 (therefore starting position in step 52 not possible):

AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMM

"Strategy" (for the old n = 16 solution)

Shortly said it is a combination of guessing and luck. It is obvious that all possibilities cannot be calculated. We can safely assume that the 1st card stays at its place, moving it would only add a rotation of cards not changing the result. Then we still have

$51! = 1551118753287382280224243016469303211063259720016986112000000000000$

possibilities. I tried to limit the possibilities and started with a $4*13$ grid, where I placed the numbers $1 .. 4$ each in a separate column. Then I filled the other numbers by adding $4$ to the number above. Example:

Testing all possibilities gave only $n=12$ as best result. Then I tried to use another grid. I increased the width until I got the posted result at the value $8$. However, one thing generates trouble for widths which aren't divisors of $52$. The grid is simply too big. The following picture shows the grid for my end result:

The green numbers are the placed $1..8$. The other values are this time the value above plus $8$. If we now use the first $52$ numbers we get numbers that are too big. I solved this problem by simply swapping the big numbers with appropriate numbers from the unused area (both marked red).

Update

For the $n = 17$ solution I also changed the direction of increments in one column.

Answer 3

I don't have a proof for the maximum number of pair-free shuffles but the following shuffle:

  19 42 32 27 51 21 10 5 44 31 4 43 8 15 18 36 23 33 52 48 14 26 6 41 9 25 12 47 38 16 3 13 24 35 20 22 50 29 28 46 17 11 45 40 30 7 34 2 39 1 49 37

produces pair-free states for the first six shuffles. The seventh shuffle produces two pairs. The following 8 lines show the initial deck and the deck after each of 7 shuffles (each preceded by the number of adjacent pairs in the deck):

  (39) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
  (0) 19 42 32 27 51 21 10 5 44 31 4 43 8 15 18 36 23 33 52 48 14 26 6 41 9 25 12 47 38 16 3 13 24 35 20 22 50 29 28 46 17 11 45 40 30 7 34 2 39 1 49 37
  (0) 52 11 13 12 49 14 31 51 40 3 27 45 5 18 33 22 6 24 37 2 15 25 21 17 44 9 43 34 29 36 32 8 41 20 48 26 1 38 47 7 23 4 30 46 16 10 35 42 28 19 39 50
  (0) 37 4 8 43 39 15 3 49 46 32 12 30 51 33 24 26 21 41 50 42 18 9 14 23 40 44 45 35 38 22 13 5 17 48 2 25 19 29 34 10 6 27 16 7 36 31 20 11 47 52 28 1
  (0) 50 27 5 45 28 18 32 39 7 13 43 16 49 24 41 25 14 17 1 11 33 44 15 6 46 40 30 20 29 26 8 51 23 2 42 9 52 38 35 31 21 12 36 10 22 3 48 4 34 37 47 19
  (0) 1 12 51 30 47 33 13 28 10 8 45 36 39 41 17 9 15 23 19 4 24 40 18 21 7 46 16 48 38 25 5 49 6 42 11 44 37 29 20 3 14 43 22 31 26 32 2 27 35 50 34 52
  (0) 19 43 49 16 34 24 8 47 31 5 30 22 28 17 23 44 18 6 52 27 41 46 33 14 10 7 36 2 29 9 51 39 21 11 4 40 50 38 48 32 15 45 26 3 25 13 42 12 20 1 35 37
  (2) 52 45 39 36 35 41 5 34 3 51 16 26 47 23 6 40 33 21 37 12 17 7 24 15 31 10 22 42 38 44 49 28 14 4 27 46 1 29 2 13 18 30 25 32 9 8 11 43 48 19 20 50

Answer 4

Probably the most simple pattern is to shift odd numbered cards along by 4 looping round to the end for cards at the start of the deck:

5 2 7 4 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 1 50 3 52

which allows 11 shuffles before pairs end up together. I feel like crazyiman's result of 12 is probably the best that can be achieved but that is just a hunch from playing with various sequences.

The code below might help test possible shuffling patterns, it has an option which is (almost) equivalent to cutting the deck after each shuffle. I wasn't quite sure if that was supposed to be part of the routine or not so it really just compares the first and last cards when checking for pairs.

/* prompt for shuffling pattern - future index of card in each position */
var P=prompt('Enter your shuffling sequence (numbers should be separated by spaces):')
       .replace(/^\s+|\s+$/g,'') .split(' ');

var cut=confirm('Cut the cards? Treats the first and last cards of the deck a being adjacent.');

/* checks a pattern uses each of the numbers 1-52 exactly once */
function check(P){ 
    var n=[];
    for(var i=1; i<53; i++) n[i]=0;
    P.forEach(function(N){ n[N]++ });
    for(var i=1; i<53; i++) if(n[i]!==1){ alert('Bad Shuffling Pattern'); throw  n; }
}

/* returns false if two adjacent cards in a deck match */
function test(d){ 
    for(var i=1; i<52+(cut?1:0); i++) if(d[i-1]==d[i%52]) return false;
    return true;
}

/* initialises a deck of cards and shuffles until test fails */
function measure(P){ 
    check(P);
    var d=fresh();
    var t=true, c=-1;
    while(t){
        d=shuffle(d,P);
        t=test(d);
        c++;
    }
    return c;
}

/* shuffles the cards according to given pattern */
function shuffle(d,p){
    var D=[];
    for(var i=0; i<52; i++) D[i]=d[p[i]-1];
    return D;
}

/* builds the pre-set new deck order */
function fresh(){
    var cards=[];
    for(var i=0; i<52; i++){
        cards[i]=(i/4)>>0;
    }
    return cards;
}

/* runs the whole test and display the result */
alert("The cards can be 'shuffled' "+measure(P)+" times before pairs end up adjacent.");

If you're not familiar with javascript read about How to open the JavaScript console in different browsers. Then copy and paste the code into the javascript console and press enter. You should be prompted for your shuffling sequence which will be checked and measured.

I've only tested this code in Chrome using crazyiman and Penguino's sequences both of which produce the expected results depending on the 'cutting the deck' option.

Answer 5

Based on what I've seen, I wouldn't be surprised if the maximum value of $N$ is as high as 37.

Like @crazyiman, I looked at generating random permutations and seeing how they did. The highest I found through random permutations was also 5, but I noticed an interesting pattern. I ended up doing 100 million iterations of choosing a random permutation and seeing how well it did, and also counted the frequency of each depth. Here's what I found (where n is the shuffle on which it has an adjacent pair):

n | count
--|------
1 | 95453225
2 | 4358185
3 | 181811
4 | 6562
5 | 212
6 | 5

The pattern here is that the ratio between counts is fairly stable:

1:2 - 21.9
2:3 - 24.0
3:4 - 27.7
4:5 - 31.0
5:6 - 42.4

The 5:6 ratio is not very reliable because neither happened very often, but it at least shows it's in the same ballpark as the other ones. Seeing as @crazyiman constructed an example that works for 12 iterations, there's no reason to believe that the pattern won't continue for a while.

Now suppose that the ratio goes up by 4 (in an attempt to underestimate $N$) each time. Starting with $N!$ and dividing by 22, 24, 28, 31, 35, 39, etc. we reach a two digit number right around the 37th division.

This is, of course, no guarantee that we can get that high, but it does suggest that it may be possible. It also doesn't rule out the possibility of an even higher maximum, but it does suggest that it is unlikely.

To help you understand why this might be possible, you have to realize that there are a lot of possible permutations:

80658175170943878571660636856403766975289505440883277824000000000000

Answer 6

I approached it with a kind-of "brute force" method (although obviously I can't try all 52! possible shuffles...). One subtle point is that the first and last card must also not be the same, because of the cut.

Instead I used a kind of "genetic" algorithm - starting with a pool of random shuffles, it selects the ones which survive for at least 4 iterations for further investigation, with a starting pool of several thousand of these.

Each surviving shuffle is mutated in 52 randomly selected ways (there are 52 x 51 / 2 different possible "mutations" consisting of having a shuffle otherwise equivalent to the last one, but with a single pair of cards swapped, so this certainly isn't exhaustive), and any that still survive at least 4 iterations are added to the processing queue.

Soon, a very significant proportion of newly-mutated shuffles are surviving 4 iterations, so it only queues the ones surviving 5... then 6, etc. For the "rarer" shuffles surviving 8 or more iterations, I also allowed for a "double mutation" (with even more of them) as well as the usual single mutation, and for the 10-iteration shuffles, a "triple mutation" (in addition to the single and double), so the memory usage exploded causing me to abort one run with about 100 million items awaiting processing, before I'd optimised the processing queue).

On one run of this algorithm, I got an 11 based on this randomised technique... but it seems more often to top out at 10 (the most recent run reported that it found nearly 18000 solutions which survived 10 iterations, probably with a handful duplicates).

I strongly suspect that 12 will in fact prove to be the maximum - primarily because there are only 13 DIFFERENT card values (we're ignoring suit for this problem). Any subset of cards having a cycle longer than 13 must necessarily contain the same card value more than once.

The program is only set to print out the FIRST solution it finds for a given minimum, but in the case where it found an 11, you can observe the evolution for the first solutions it found for 8,9,10,11...

Answer 7

While brainstorming on this, I think I can establish an absolute maximum upper bound.

There are $52$ cards in the deck, and for each one, it needs to be adjacent to one of only $49$ of the remaining cards. If we only examine the head node of the string, we can ignore the fact that the last card of the deck SHOULD not be a duplicate of it, and that prevents us from narrowing it down even further, but the rest of the deck has to follow those rules, so it still matters. (visualize the deck as a loop and it helps)

I can establish that the absolute maximum number of iterations of the algorithm is $49$.

in iteration $#0$ (the "unshuffled" state), all cards are adjacent to 1-2 of their number. (each $7$ is adjacent to another $7$, and up to $2$ of them). After the first application of the algorithm, each card must be adjacent to $0$ of their number. Each successful application of the algorithm must make "progress" until you reach $#25$ iterations, when it starts to regress back towards the initial state. Iteration $#49$ would be one of three straight where every number would be adjacent to another of its number, leading to iteration $#52$, which is the same as iteration $#0$. At iteration $#25$, it must be therefore at "maximum" "randomness".

In this particular incident, the nonrandomness of the deck would be RIDICULOUSLY OBVIOUS, however. It would start off looking something like $12121212343434345656565678787878$ and for FOUR STRAIGHT SESSIONS OF GAMES IN BETWEEN SHUFFLES, you would be looking at the EXACT SAME OPENING HAND but with the suits changed.

That being said, I can't think of an algorithm that would cycle only the suits three out of every 4 "shuffles". So this is pretty much the extent of my input on the subject until I get bored enough to code it.

Also to note: If there is no way to "shuffle" between suits for 3 out of 4 "shuffles," then this serves as proof that $12$ is the upper bound, because that's the only way to expand beyond the simple problem of regression back towards the initial state. But I'm sure someone can explain it more eloquently than I can.

Answer 8

I have pretty much no idea, but i would like to try this:

1 5 9 13 17 21 25 29 33 37 41 45 49 2 6 10 14 18 22 26 30 34 38 42 46 50 3 7 11 15 19 23 27 31 35 39 43 47 51 4 8 12 16 20 24 28 32 36 40 44 48 52

I have no idea on what n is though... I'll edit it when I know.