A card-rearranging problem on the Riddler blog. Here it goes:

You play so many card games that you’ve developed a very specific organizational obsession. When you’re dealt your hand, you want to organize it such that the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent. (Numbers don’t matter to you.) Moreover, when you receive your randomly ordered hand, you want to achieve this organization with a single motion, moving only one adjacent block of cards to some other position in your hand, maintaining the original order of that block and other cards, except for that one move.

Suppose you’re playing pitch, in which a hand has six cards. What are the odds that you can accomplish your obsessive goal? What about for another game, where a hand has N cards, somewhere between 1 and 13?

Here is my solution:

[Show Solution]

I was unable to find an analytic or closed-form expression for the solution to this problem, so I’ll present an old fashioned brute-force solution. The idea is simple:

- Enumerate all possible hands
- For each hand, enumerate all possible moves that consist of moving some group of adjacent cards to somewhere else in the hand.
- If any such move succeeds in sorting the hand, mark the hand as “good”.
- Once we’re done, count all “good” hands and divide that by the total number of hands

Simple, right? I’d like to point out is that this is not an approximate solution; there is no simulation involved. I’m counting all the possible scenarios, so this approach produces the exact answer. The only problem is that there are a *lot* of hands to check, and the bigger the hands get, the longer it takes to check them, since there are more possible moves. Successfully solving this problem requires coding it up in a way that a computer can find the solution in a reasonable amount of time. In order to make this work, I used several tricks to reduce the computation required:

- We don’t have to enumerate
*all*possible hands because only the suits matter, but we do have to be careful about how we count. We begin with a full deck of cards (52 distinct cards). Let’s suppose we want to count hands of size 2. There are $52\cdot 51 = 2652$ possible hands. But since numbers don’t matter, we can remove the number and just look at suits. There are then 16 possible hands:

\[

\begin{array}{cccc}

♠♠ & ♠♣ & ♠\color{red}{♥} & ♠\color{red}{♦} \\

♣♠ & ♣♣ & ♣\color{red}{♥} & ♣\color{red}{♦} \\

\color{red}{♥}♠ & \color{red}{♥}♣ & \color{red}{♥}\color{red}{♥} & \color{red}{♥}\color{red}{♦} \\

\color{red}{♦}♠ & \color{red}{♦}♣ & \color{red}{♦}\color{red}{♥} & \color{red}{♦}\color{red}{♦}

\end{array}

\]suppose for example that the hands with different suits but same color are not sortable. There are four such hands: $\{ ♠♣, ♣♠, \color{red}{♥}\color{red}{♦}, \color{red}{♦}\color{red}{♥} \}$. Then we might conclude that $\tfrac{4}{16} = 0.25$ of hands are not sortable. But this would be wrong! (thanks to Guy Moore for pointing this out). The reason is that these 16 hands don’t all occur with equal probability. There are $13\cdot 13 = 169$ ways of picking two cards of different suits, but only $13\cdot 12 = 156$ ways of picking two cards of the same suit! So each type of card should be weighted by its likelihood of occurrence. This means the probability of picking an unsortable hand should really be:

\[

\frac{4\cdot 169}{4\cdot 156 + 12\cdot 169} = \frac{13}{51} \approx 0.2549

\]So we can collapse the large number of possible hands to this more manageable size as long as we compensate by appropriately weighting the different items. In combinatorics, this collapsed group of cards (where we care about the order and the suit, but not the number of the card) is an example of a multiset permutation.**Note:**If we don’t weigh the hands according to likelihood (i.e. assume all hands are equally likely), this is equivalent to assuming the deck has infinitely many cards (but the same number of cards in each suit). - Adjacent cards of the same suit can be collapsed to a single card. This is because there is never any benefit to moving a block of cards if it splits an existing contiguous block. So for example:

\[

\{♠,♠,\color{red}{♥},\color{red}{♥},\color{red}{♦}\} \implies \{♠,\color{red}{♥},\color{red}{♦}\}.

\]This greatly reduces the computations because if two different hands collapse to the same reduced hand, we only need to do the work for one of them! In computer programming, this technique of storing the values of computations so that you don’t end up computing the same thing many times is called memoization. - If a hand consists of $N$ cards (after we collapse adjacent suit repetitions as described above), then there are $\binom{N+1}{3}$ possible moves we can make. This is because every move is characterized by three locations. I’ll illustrate this with an example. Say our hand looks like this: $\{♠,\color{red}{♥},\color{red}{♦},♠,\color{red}{♥},♣\}$ and we want to sort it by moving cards 4 and 5 and inserting them between cards 1 and 2. In other words, we want to perform:

\[

\{♠,\color{red}{♥},\color{red}{♦},(♠,\color{red}{♥}),♣\} \implies \{♠,(♠,\color{red}{♥}),\color{red}{♥},\color{red}{♦},♣\}

\implies \{♠,\color{red}{♥},\color{red}{♦},♣\}

\]where we did one final collapse at the end. This transformation can be represented by inserting three “bars” between cards as follows. Then the swap simply consists of exchanging the cards between the two pairs of bars! Here is the diagram:

\[

\{\,♠\,\,|\underbrace{\color{red}{♥}\,\,\color{red}{♦}}_\text{swap this}|\underbrace{♠\,\,\color{red}{♥}}_\text{with this}|\,\,♣\,\}

\implies \{♠, ♠, \color{red}{♥},\color{red}{♥},\color{red}{♦},♣\}

\]Each triplet of bars corresponds to a possible swap, and we can insert bars in $N+1$ possible spots (in between each card and on either end). - If the hand has 8 or more cards in it after we perform the collapse, then it’s impossible to sort it in one move. This is because our final hand can have at most 4 groups of cards in it, and a single move can cause at most 3 collapses. With 8 cards, we can get down to 5 but not 4. Here is an example of a 7-card hand that can be sorted in one move:

\[

\{\,♠\,|\,\color{red}{♥}\,♣\,|\,♠\,\color{red}{♥}\,|\,♣\,\color{red}{♦}\,\}

\implies \{\,♠\,♠\,\color{red}{♥}\,\color{red}{♥}\,♣\,♣\,\color{red}{♦}\,\}

\implies \{\,♠\,\color{red}{♥}\,♣\,\color{red}{♦}\,\}

\]

### Numerical results

There was a bit of confusion as to how to interpret the meaning of the requirement “the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent”. One way to interpret this statement is that we only require cards of a different suit but same color to be separated if it’s actually possible to separate them. For example, the two-card hand $\{\color{red}{♥}\,\color{red}{♦}\}$ counts as being sorted because there are no spades or clubs that can be placed between the heart and the diamond. In this scenario, here are the results:

Note that hands of up to size $N=4$ are always sortable in one move. The exact solution for the case $N=6$ using this interpretation is $\tfrac{51083}{83895} \approx 60.8892\%$. Another way to interpret the requirement is that cards of a different suit but same color can never be adjacent. This means that hands like $\{\color{red}{♥}\,\color{red}{♦}\}$ are never sortable no matter what you do. In this case, we get the result:

It’s interesting to note that the probability of a “sortable” hand in this interpretation actually reaches a maximum when $N=4$ and then decreases afterwards. The exact solution for the case $N=6$ using this interpretation is $\tfrac{1735996}{2936325} \approx 59.1214\%$.

I wrote my code in Julia, and you can view my notebook here. The computation gets slower in an exponential fashion as we increase $N$. The cases $N \leq 8$ take on the order of seconds, but computation time quadruples every time $N$ increases by 1. The last case, $N=13$, took about 40 minutes! While there is a significant amount of computation to do, there is also significant computational overhead due to using exact arithmetic instead of making approximations. For this, I used Julia’s BigInt datatype. So the solutions I obtained were exact. For example, the probability of a sortable hand for $N=13$ (using the first interpretation) turns out to be:

\[

\tfrac{10954472929065768960}{3954242643911239680000} = \tfrac{30785713171}{11112737293000} \approx 0.27703\%

\]Using approximations the whole way leads to a computation time of less than 10 minutes for the most complicated case.

Laurent,

Nice work, as always! But in looking at your bar graph of the results, I don’t see why the probability for N=2 and N=3 wouldn’t be 1. If you have two cards, don’t they automatically meet the goal without any movement necessary? If you have three cards, I think you could always move one card (if necessary) to achieve the goal of uniting two cards of the same suit.

Not quite — One of the criteria is that adjacent cards of a different suit must also be a different color. So if a two-card hand consists of a heart and a diamond or a spade and a club, it can never be sorted…

Ah but now I see what you mean. My interpretation was that the “different colors” requirement was a hard constraint, as opposed to “it’s only a hard constraint if it’s possible”. Words are hard.

As a law professor, I couldn’t agree more with you that words are hard! Making the shift from math and physics grad student to law student was a challenge, and it still is.

Actually, aren’t all hands for N=1-4 sortable in one move? I am assuming hands with only red or black suits are counted as sortable (HHDD, CCSS, etc). But maybe that’s not that clear from the puzzle.

“When you’re dealt your hand, you want to organize it such that the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent.

I took this to mean that single color hands could be sorted. But it is confusing.

That’s how I read it:

(1) if the hand is single-colored, this condition doesn’t apply; but

(2) if the hand is bi-colored, then suited groups of the same color must be separated.

I updated my blog post to reflect the two possible interpretations.

I included a plot for both cases.

Thank you all for the feedback!

Hi Laurent,

I think there is a small error in your solutions.

You have treated each suit as equally likely. But in fact, as soon as I draw one card from a suit, drawing another is less likely, since there are fewer left. For instance, I find that the probability of failing, in the “strict” reading, when there are 2 cards, is 13/51, whereas your result is 13/52=1/4. The reason is that, if I first draw a heart (say), there are now 12 hearts, 13 diamonds, and 26 black cards I can draw. The chance of drawing a diamond, and thereby failing, is 13/51, not 1/4. Similarly, with 3 cards, I lose precisely when I draw two from one suit and a third from the other suit, in any order. The probability to do so is not 3/16=.1875, it is 3*13*12/(51*50) = .183529..

Other than that, it’s a nice solution!

Ah you’re absolutely correct. Treating the hands as multisets by collapsing all the numbers doesn’t work. I could probably fix my approach if I weighted each multiset by its probability of occurrence. e.g. if my suits are (S,H,C,D) and we take the 2-card case, the multiset approach says there are 16 possible hands: {SS, HH, CC, DD, SH, HS, SC, CS, SD, DS, HC, CH, HD, DH, CD, DC}. Exactly 4 of those have adjacent suits of the same color: {SC, CS, HD, DH}. That leads to 4/16 = 1/4, which is incorrect as you pointed out. There are 13*12 ways of getting SS, HH, ect, but 13*13 ways of getting SC, CS, etc… If we weight each one by its respective likelihood, that yields:

\[

\frac{4\cdot 13 \cdot 13}{4\cdot 13 \cdot 12 + 12\cdot 13 \cdot 13} = \frac{13}{51}

\]which is the correct probability. If I can find the time over the next few days I’ll see if I can fix my solution to incorporate these weightings.

Thanks!!!

I edited my blog post once more. This time I think the solution should be correct. As Guy Moore pointed out, I had ignored the fact that not all hands are equally likely to occur. Re-weighing each hand by its likelihood of occurrence fixed the issue. Thanks for the comments!