Gamingdeputy reported on February 11 that Liu Qian’s magic performance in this year’s Spring Festival Gala aroused heated discussions among netizens. The official public account of Peking University gave a detailed interpretation and revealed the mathematical problem behind it – the “Joseph problem”.
Magic steps:
Step 1: Tear the 4 prepared playing cards into two equal parts and stack them together.
Step 2: Move the number of cards from the top of the deck to the bottom of the deck.
Step 3: Place the first three cards in the middle of the deck and remove the top card from the deck and set it aside.
Step 4: Take out a few cards from the top of the deck and insert them into the middle of the deck. The number of cards chosen here is 1 for southerners, 2 for northerners, and 3 if you are not sure whether it is southerners or northerners.
Step 5: The boy throws away the top 1 card of the card pile, and the girl throws away the top 2 cards of the card pile.
Step 6: Perform the “Miraculous Moment” cycle, taking the top card of the deck and placing it on the bottom of the deck after each word.
Step 7: Starting from the top of the deck, put the top card on the bottom of the deck each time, then throw away the top card. Repeat the above operations until there is only one card left. Check this card. Does it match the card placed aside? If they match, the magic is successful.
Magic steps revealed:
step one
Advertisement
We let the selected four playing cards be 1234 respectively. After tearing them apart, two sets (half cards) of playing cards were produced, which were numbered 1234. After being stacked together, they formed a set of playing cards numbered 12341234 from top to bottom. Stack of playing cards.
Step 2
At this point we can notice that no matter how many cards we move from the top of the pile to the bottom, the obtained poker pile number (Gamingdeputy Note: from top to bottom) will only have the following results:
Advertisement
12341234 (the number of characters in the name is evenly divisible by four)
23412341 (the number of characters in the name modulo four plus one)
34123412 (the number of characters in the name modulo four and two)
41234123 (the number of characters in the name modulo four and the remainder is three)
Observing the above possible card piles, we can find that the generated card piles have the following properties:
1. The order of the first four cards and the last four cards are exactly the same.
2. The first four cards and the last four cards are a rotation of 1234 respectively.
Step 3
From this step on, we only consider the fourth and eighth cards in the current deck, which are marked as X, and the other cards are marked as 0. Then based on the discussion in the previous step, we can get the current deck shape as:000X000X.
After placing the first three cards in the middle of the deck, no matter where the three cards are placed, the resulting deck will be:X000000X.
Thus, the card selected for matching will be X, and the other card that matches it (called the target card) will be at the bottom of the deck.
Step 4
After the previous step, the deck is numbered 000000Xtherefore, no matter how many cards on the top of the selected deck are inserted into the deck in this round, it will not affect the position of the target card, and it will still be at the bottom of the deck.
Step 5
At this time, the boy's deck is:00000X.The girl's deck is:0000X.
Step 6
Through experimentation, we can know that after step 6, we will get the following deck:
Boys: 0000X0
Girls: 00X00
Step 7
At this point, Liu Qian's magic steps have been revealed. Peking University further explained that this is actually a “Joseph problem”:
Suppose n people numbered 1, 2,…, n form a circle, start counting from the first person, stop counting when m is reached, and the person who reported m leaves the circle. Then start counting again from the next person, stop counting when m is reported, and report m's exit from the circle… Follow this rule until everyone is out of the circle. Ask for the number of the last person left.
In order to simplify the problem, we consider the situation where n people are numbered from 0 to n-1, and one person exits every m people. We call it the (n,m) problem. After the first person (that is, the person whose number is congruent m modulo n) exits, the remaining n-1 people are renumbered, so that the k number of the new problem corresponds to the k+m number in the original problem. Therefore, the solution to the (n, m) problem is J (n, m) = J (n-1, m)+m and J (1, m) = 1 (modulo n). Accordingly, J (n, m) can be obtained through recursion. In practice, Joseph's problem is generally solved using code. Liu Qian's magic uses the special case of m=2.