A deck of $52$ cards is given. There are four suites each having cards numbered $1,2,\dots, 13$. The audience chooses some five cards with distinct numbers written on them. The assistant of the magician comes by, looks at the five cards and turns exactly one of them face down and arranges all five cards in some order. Then the magician enters and with an agreement made beforehand with the assistant, he has to determine the face down card (both suite and number). Explain how the trick can be completed.
Problem
Source: RMO Delhi 2016, P6
Tags: combinatorics, Game Theory
11.10.2016 13:56
I think this problem is given less attention than it should get. Anyway... The trick is this: Some two cards among the five have same suite; put them in the first and second places from the left (assuming all cards are arranged in a row) such that the number of steps one needs to go from the number at the first card to the number at the second card when moving clockwise on a circle labelled $1,2,\dots, 13$ in that order is at most $6$. Clearly, this can be done for at least one ordering of the two cards. Let this number be $N$. Put one of them face down. Now, the cards at third, fourth and fifth positions have distinct numbers on them so there are $6$ ways to arrange. Let each arrangement correspond to a number from $1$ to $6$ agreed previously, and the assistant arranges these such that this number is $N$. Now, the magician enters. Seeing the first and second cards, he can find the suite of the face down card. Obtaining the number $N$ from the third, fourth and fifth cards and the value of the face-up card among the ones at the first and second place, he can determine the value of the face down card. $\square$
11.10.2016 15:16
anantmudgal09 wrote: Seeing the first and second cards, he can find the suite of the face down card. I don't quite get this. How can he find the suite of the face down card from this?
11.10.2016 15:39
He looks at the cards in position #1 and #2. They were arranged to have same suite by the assistant, and one of them is face-down. Looking at the face-up card (and knowing for a fact what the assistant did), he can get the suite. Is it still unclear?
11.10.2016 16:04
anantmudgal09 wrote: He looks at the cards in position #1 and #2. They were arranged to have same suite by the assistant, and one of them is face-down. Looking at the face-up card (and knowing for a fact what the assistant did), he can get the suite. Is it still unclear? OK. I get it know. Thanks. Another trick can be use: The assistant can pick any card. The other four cards can be arranged in order so that the magician knows which order assign to which number from $1$ to $13$ .For example, they discuss the orders of four numbers $1,2,3,4$ where each permutation assign to a number from $1$ to $13$ (they only need to assign orders of cards numbered $1,2,3,4$ to fill up $13$ numbers). After that, the four cards the assistant received from audience can be mapped to $1,2,3,4$ by their number from smallest to largest. So the magician can guess the number of hidden card from $4$ known cards. In order to find the suite, the assistant put the hidden card between the $4$ known cards and since there are $5$ gaps between four cards, the magician can find the suite for hidden card (for example if the order is $1N234$ then the hidden card $N$ is in suite number $2$). This trick can be also apply if 1) The number of cards can be $5 \times 13$ and number of suites are $5$. 2) The audience is the one who pick the face down card (not the assistant) but the assistant knows its number and suite. 3) The magician only know the numbers of the $4$ cards but not their suites.
11.10.2016 21:17
That's a really nice solution @shinichiman.. I wrote my idea of using php for suite . and I used php on parity(7odd,6even ,etc..)so that the magician knows the suite as well as the parity(even,odd) of the face down card for sure.. Couldn't come up with a way to find the number with surity....will I get any points..?
12.10.2016 05:35
Sorry, did I do something wrong? The trick can be done even if the audience turns a random card down. Just note that since the values are all distinct, then there can be $5!=120$ distinct ways to send a signal. Since there are only $52$ cards, clearly there are enough distinct signals to determine the face-down card.
12.10.2016 06:19
It turns out that it is still possible to determine the hidden card's identity even if the assistant, after choosing the "face down" card, removes it and then rearranges the remaining four cards, so that the magician only sees a rearrangement of four cards instead of five cards. This is a harder problem though.
12.10.2016 07:55
Naysh , please do give us the solution to this new problem you mentioned
12.10.2016 10:43
Naysh's variant is a classic interview question. For It, anatmudgal solution still applies. Follow his method and remove the face down card instead of placing it down. Then we can still determine its identity.
12.10.2016 11:01
bobthesmartypants: That is an heuristic suggesting the problem should be possible, but it does not solve the problem because you need to guarantee no overlap between the signals sent for different sets of five cards.
EDIT: woops, got sniped. Though the solution above generalizes to a much larger deck.
12.10.2016 11:45
This is a common question. I had read the solution somewhere before RMO
12.10.2016 12:53
MellowMelon wrote: bobthesmartypants: That is an heuristic suggesting the problem should be possible, but it does not solve the problem because you need to guarantee no overlap between the signals sent for different sets of five cards. I think there is no problem for his solution since we are given alot more freedom in the original question as we are able to place the faced down card too, letting us be able to convey $5!$ possible different pieces of information. Of course this doesn't work for the variant since we are only allowed $4$ cards to play around with. @above: You can even google it by searching "5 card magic trick"
12.10.2016 13:02
I believe bobthesmartypants' existential solution is correct. However, the problem asks: "Explain how the trick can be completed" so it could possibly mean to show an explicit strategy. Still, there being a lot of freedom; i think it is valid.
12.10.2016 13:07
@above: You can just enumerate the permutations by lexicographic order while letting the faced down card be the largest/smallest. However for the variant, Hall's Marriage only gives existence and it is much harder to show an explicit strategy (plain brute-force will not work since you will have to choose wisely.)
18.12.2016 19:10
Another solution!!! Use PHP to choose the suite. To choose the number, use binary, for eg, let the last four cards be in landscape(say 0) or potrait( 1) orientation. Any number from 1 to 13 can be shown in such a way.
18.12.2016 20:25
MellowMelon wrote: bobthesmartypants: That is an heuristic suggesting the problem should be possible, but it does not solve the problem because you need to guarantee no overlap between the signals sent for different sets of five cards. Actually, I think there is no problem at all. No matter what cards we have we can label them as cards $0, 1, 2, 3, 4$ where $0$ is the face-down card and $1, 2, 3, 4$ are the other cards in increasing value order. Then we have $120$ distinct ways to arrange these values, so take the first $52$ and biject them to the $52$ cards. The rest of the permutations will never be arranged at all.
21.09.2017 18:01
~~~~~~~~
17.09.2018 06:52
My solution.. At the leftmost place keep the face down card.At it's immediate right keep the card with same suite.By PHP 2 cards have same suite. One of the cards having same suite is over turned. Now assume a imaginary line passing through the centre of face down card.The assistant places some card above this imaginary line and some below this line.Cards above the line are coded as 1 and below as 0.The magician starts reading the binary formed from right and can get the number of the face down card.All base 10 no. from 1 to 13 can be represented by using 4 digits only.Here cards are acting like digits.
01.10.2023 14:24
anantmudgal09 wrote: I think this problem is given less attention than it should get. Anyway... The trick is this: Some two cards among the five have same suite; put them in the first and second places from the left (assuming all cards are arranged in a row) such that the number of steps one needs to go from the number at the first card to the number at the second card when moving clockwise on a circle labelled $1,2,\dots, 13$ in that order is at most $6$. Clearly, this can be done for at least one ordering of the two cards. Let this number be $N$. Put one of them face down. Now, the cards at third, fourth and fifth positions have distinct numbers on them so there are $6$ ways to arrange. Let each arrangement correspond to a number from $1$ to $6$ agreed previously, and the assistant arranges these such that this number is $N$. Now, the magician enters. Seeing the first and second cards, he can find the suite of the face down card. Obtaining the number $N$ from the third, fourth and fifth cards and the value of the face-up card among the ones at the first and second place, he can determine the value of the face down card. $\square$ bro what about the suite?
01.10.2023 14:36
here is my 90000iq solution. pls let me know if anything is wrong. so the assistant will put the face down card in either the 1st 2nd 3rd or 4th position in the deck. 1st position corresponds to hearts, 2nd to spades, 3rd to dice and 4th to clubs. this tells the magician the suite. now the magician removes the face down card and looks at the other four cards. let their numbers be a1<a2<a3<a4 (as all numbers are distinct). now the remaining cards can be arranged in a total of 24 (4!) ways. so, using this knowledge, the magician and assistant can agree to associate certain permutations of a1 a2 a3 and a4 to certain values. for instance, the assistant will be told to put down the greatest card in the deck. so the possible values of the card put down are 5 - 13. so when you exclude the card put down, we can use the order of the remaining cards to determine the mystery card. for instance, we can associate the order a1 a2 a3 a4 with the number 5, a1a2a4a3 with 6 and so on. so each number has its unique identification and this will work regardless of what the other numbers actually are, as we are only interested in what is larger and what is smaller. hence, even though the magician and his assistant have to mug up a lot of values, they can get the trick done this way. (ps it works even if the audience chooses which card to put down as long as the assistant gets to arrange the deck)
21.10.2023 14:38
I guess the condition of the distinct number is not needed as we can number each card by a 3-digit system $abc$ where $a$ is 1,2,3,4 denoting the suite of the card and the number on the card is denoted by $bc$ in the decimal system as usual. I am also adding an additional constraint that the face-down card, though the assistant knows its suite and number, cannot be used in the sequence. Say that the card is "given away" instead of face-downed. Now note that while all cards with numbers $1,2,...,13$ are arranged in a circle, we can move clockwise from one card to another by $6$ "moves".Now the trick is by PHP we can guarantee that two cards will have the same suit and The assistant will take one of those cards and will give away the one from which to go to the other one we have to move clockwise and note that the number of moves is at most $6$.Now by the suit of the first card in the sequence, the magician will know the suit of the given away card, and from the numbers on the rest three, he can arrange them and encode six numbers from $1$ to $6$. He will add that encoded number with the number on the first card and take mod $13$ to get that number of the given away card. And it does not work if the audience chooses the card to be "given away".