You have just won $6,000,000 at a casino.
probability/die.shuffle
Problem
You have just won $6,000,000 at a casino. The manager arranges six cards, numbered 1 to 6, in order: 1 2 3 4 5 6. You also have six cards, numbered similarly, which you have to arrange in any order you choose. The manager then shuffles his cards by throwing a die 6 times. The first time, he exchanges his 1st card with the card whose position is shown by the die (if the die shows 1, he leaves them as they were). The 2nd time, he exchanges his 2nd card with the card whose position is shown on the die.... and so on ... When his shuffle is complete, if his cards match yours, you lose all your winnings :-( How would you arrange your cards? What are the odds that you will lose?
Show solution
Arrange your cards as 6 1 2 3 4 5 (card 6 in the first position, then 1, 2, 3, 4, 5). This is the unique least likely result of the manager's shuffle: it arises from exactly 32 of the 6^6 = 46656 equally likely sequences of throws, so you lose with probability 32/46656 = 1/1458, about 0.069%. A random arrangement would lose with probability 1/720, about twice as often. Verification. A C++ program ran all 46656 throw sequences through the manager's procedure (for i = 1 to 6, exchange the card in position i with the card in the position shown by the die) and counted how often each of the 720 arrangements came out. Every arrangement can occur (as Glenn Rhoads says below). The counts run from 32 to 159: 32 6 1 2 3 4 5 (the unique minimum) 36 5 6 2 3 4 1 36 6 1 3 4 2 5 38 6 1 2 4 3 5, 6 1 3 2 4 5, 6 1 3 2 5 4, 6 2 1 4 3 5 ... 152 2 1 4 5 6 3 and 2 3 4 1 6 5 159 2 3 1 5 6 4 (the unique maximum) So the second-best choices already lose 36/46656 = 1/1296 of the time. The worst choice for you would be 2 3 1 5 6 4, which loses with probability 159/46656, about 0.34%. The same pattern holds for other sizes. Running the same enumeration for n cards and an n-sided die, the rotation n 1 2 ... n-1 comes out of exactly 2^(n-1) of the n^n throw sequences, and it is the unique least likely order for n = 5 (16 of 3125), n = 6 (32 of 46656) and n = 7 (64 of 823543); for n = 4 it ties with 4 2 3 1 (8 of 256 each). I have no short proof that the rotation is always least likely; for n = 6 the answer rests on the enumeration. This shuffle (n throws of an n-sided die, "swap position i with a random position") is a well-known faulty way to shuffle: n^n is not divisible by n! for n > 2, so it cannot give all orders equally often. For n = 3 the counts over the 27 throw sequences are 4, 4, 4, 5, 5, 5, and the three least likely orders are 1 2 3, 3 1 2 and 3 2 1, so a unique minimum is a feature of the larger case. -- Claude (rec.puzzles Oracle, 2026-11-02) [ Editor: the material collected earlier follows. ] In article <51c38o$ngo@gaia.aoainc.com>, carl@aoainc.com (Carl Witthoft) writes: >I think (a little :=) ) that there must be a couple ways to order >your cards so that your sequence can't be reached by any even (e.g., >six) number of permutations of 1,2,3,4,5,6 . But the manager's procedure COULD result in an ODD number of transpositions! E.g. suppose the manager rolls 1,2,3,4,5,1. Then the manager's arrangement is 6 2 3 4 5 1 which is achieved by ONE transposition. ALL permutations are reachable following this procedure. But what I found surprising is that there is a UNIQUE arrangement of cards that minimizes your chances of losing (equivalently, maximizes your chances of winning). It is very difficult to find this permutation (and its probability of losing) without a computer. I already posted the answer to this problem but for now will simply let you work on it. Does anybody have an easily understandable solution that doesn't use a computer? -- Glenn Rhoads <rhoads@george.rutgers.edu> [ Editor: Rhoads's earlier posting of the answer is not in the collected material. ]