Current location - Training Enrollment Network - Mathematics courses - How many times do I have to wash the cards before I can wash them thoroughly?
How many times do I have to wash the cards before I can wash them thoroughly?
Three shuffles are not enough. Never think that you can wash your cards after two or three times. Many card tricks use the secret that shuffling cards three times is far from complete. For example, if I give you a new deck of cards, you are responsible for shuffling the cards. Wash it once. Wash it again. You don't think it has been washed, do you? Then wash it again. Then, please sneak a look at the top card, write down its color and points, and then insert it in the middle of this pile of cards and give me the whole deck. I can pick out this passive card. The principle of magic is as mentioned above: washing a stack of orderly cards for three times will not completely confuse the whole deck of cards, and the order will be very regular. Moving the position of the top card will break this rule and expose clues. For the convenience of further explanation, let's take 13 card as an example. As this is a new deck of cards, the cards of 13 are in order from the beginning: washing the cards once is equivalent to dividing the above sequence into two halves, and then interlacing them to form a new sequence: therefore, after washing the cards once, look for A, 2, 3, ..., J, Q and K in turn, and you will find that they form two "ascending sequences" (respectively, if. You will find that this will break the law of "four ascending sequences", so it is easy for us to recognize that in the following playing card sequences, 7 should have been placed at the back: but in the above example, these ascending sequences are very short, and the theoretical average length is only 13/4 = 3.25. So if the opponent's shuffling skills are not good, the magic may make mistakes. However, if 52 cards are washed three times, eight ascending sequences will be generated, and the average length of each ascending sequence is 52/8 = 6.5, so the problem of magic performance will not be great. Five shuffles have washed uneven cards. We can use the idea of "ascending order" to prove that five shuffles can't completely wash the cards, because some permutations can never be obtained only by five shuffles. We assume that the initial order of playing cards is 1, 2, 3, …, 5 1, 52. After five shuffles, a maximum of 25= 32 ascending sequences will be generated. However, the arrangement of 52,565,438+0, …, 3,2,654,38+0 has 52 ascending orders, so this arrangement will never be washed out after five shuffles. In fact, all the arrangements of more than 32 ascending sequences can't be shuffled for five times, which proves that five shuffles can't wash even cards. Looks like it's going to be shuffled six times. Seven shuffles are enough. So, how many times do you have to wash it to make all the arrangements have roughly the same probability? Don't tell me that someone has really done such research. 1992, Persi Diaconis, an American mathematician and professional magician, together with Dave Baer of Columbia University, established a mathematical model for the cross-shuffling method, analyzed the arrangement properties of playing cards including ascending order, defined the "total variation distance" between the arrangement distribution and the average distribution obtained after m shuffling, and finally published a 20-page paper. They calculated that when there are 52 playing cards, the shuffling times are 1, 2, ..., 10, and the total variation distances are 1.000, 1.000, 0.000 respectively. It can be seen that five shuffles can make the whole deck random, and the randomness will increase significantly until the seventh shuffle; And after that, the total change distance will decrease in turn at a ratio of about 1/2. So their conclusion is that seven shuffles are random enough. They also analyzed the problem in an asymptotic sense: when n is large enough, the number of shuffles required is about 3 log2n/2.