Is this 10-card magic trick possible?

Question

A magician (Yes, that's you) has 10 cards, say labelled 0 to 9. Now, the magician's assistant and the magician perform a magic trick:

1. The magician turns around (so he can't see the cards)
2. A volunteer from the crowd comes up and arranges the ten cards in any order they want
3. The assistant picks four cards and asks the volunteer to flip them over without changing the order, so they are now facedown (now we have four facedown and six faceup cards). The assistant leaves the stage (i.e. does no further communication with the magician, verbal or otherwise)
4. Now the magician turns around and works out what each of the facedown cards is

The audience applauds!

So the question is how did the magician (you) do it?

Of course, you talked to your assistant beforehand and decided on a strategy - what is the strategy?

---

I'm not 100% sure it's possible, although I am pretty confident (90%) it is. The best I've got has a >50% (not sure of the exact amount) chance of succeeding, which may even be 100% although I haven't checked.

Answer 1

Here's a strategy that works 100% of the time, requires no communication with the assistant other than the selection of face-down cards, and is simple enough to memorise (if fairly complex to work out in realtime):

General principles

The five cards are divided into five groups of two: A = {0,1}, B = {2,3}, C = {4,5}, D = {6,7}, E = {8,9}. These have a cyclic sequence, A→B→C→D→E→A, thus each group has a "next group". We convey information primarily via which groups have cards turned face down, and how many, although the selection of cards within groups is also used to convey a little extra information.

The assistant's strategy

The assistant starts by turning the rightmost card face-down, unconditionally. The assistant also turns the other card in the same group face-down. Call this group P, and the other four groups Q, R, S, T in cyclic order.

Next, the assistant checks two properties of the original permutation: whether the permutation is even or odd (i.e. requires an even or odd number of pairs of elements swapped to produce 0,1,2,3,4,5,6,7,8,9), and whether the rightmost element is even or odd. If the permutation is even, the assistant turns a card in group Q face down; if it's odd, the assistant turns a card in group R face down. The card turned face down this way has the same parity as the rightmost card of the original permutation (the first one we turned face down).

Finally, the assistant considers the second and third cards turned face down (i.e. the face-down cards that aren't in the rightmost position), plus three face-up cards: both cards in group S, and the smaller card in group T. If we consider only these cards, we have a list of five cards, the "reduced list". Consider this reduced list bent around into a circle: exactly two cards will be face down, and either adjacent to each other or with a card in between. If there's a card in between them, turn it face down. Otherwise, turn the "opposite card" in the circle (the one that has distance 2 from both cards in the reduced list) face down.

The magician's strategy

First, the magician identifies which of the groups A,B,C,D,E corresponds to P,Q,R,S,T. This is fairly easy: group P is the group with two cards face down, and the rest can be calculated in cyclic order from there.

Next, the magician works out the identity of the rightmost card. Groups Q and R have one face-down card between them, which has the same parity as the rightmost card. We know the rightmost card is in group P, so there's only one possibility.

The next thing to work out is which of the face-down cards is in group S or T. By elimination, we know which numbers the face-down cards have, and thus we can pinpoint where the five elements of the reduced list are within the list as a whole (two of them will be face-up and can be identified directly, the other three are the three face-down cards that aren't at the rightmost end of the full list). Considering the reduced list to be cyclic, if all three face-down cards are adjacent, the group S/T card must be the one in the middle of the three adjacent face-down cards; otherwise, it must be the one that's on its own (with the other two forming a pair).

The magician now knows the identity of 8 cards (the 6 face-up cards, the card at the rightmost end of the original list, and the face-down card from group S/T (because its position is known, and with three face-up cards from groups S/T, its value can be deduced by elimination)). Thus, there are only two face-down cards left, each of which can only have two possible values, i.e. there are only two possible original permutations, which are one swap away from each other. This means that one of the possibilities is an even permutation, and the other an odd permutation. We can check to see whether group Q or R has a face-down card, and thus know the parity of the permutation we want, and that eliminates one possibility, leaving us with only one possibility for the order of the original list.

Example

As an arbitrary example, let's take the sequence 0492753816 (which @Trenin suggested as a counterexample to a different proposed strategy).

The assistant reasons like this:

• The rightmost card is 6, meaning our groups are P=D={6,7}, Q=E={8,9}, R=A={0,1}, S=B={2,3}, T=C={4,5}. Turn both cards in group P face-down, giving 0492?5381?.
• The rightmost card is even, and the permutation is even (e.g. 0492753816 → 0192753846 → 0129753846 → 0123759846 → 0123459876 → 0123456879 → 0123456789 is six swaps, an even number; it's known mathematically that any sequence of swaps that maps one permutation to a specific other permutation must always have a length of a specific parity, so an even-length sequence of swaps existing proves an odd-length sequence of swaps can't). As such, we hide the even (even rightmost number) element of group Q (even permutation); that's the 8, giving us 0492?53?1?.
• The reduced list consists of the hidden 7 and 8, plus both cards in group S (2 and 3), and the smaller card in group T (4). That's 42?3?. The hidden cards aren't adjacent, even viewing this list cyclically, so we hide the card between them; that's the 3.

The sequence of cards left on the table is therefore:

0492?5??1?

The magician reasons like this:

• Out of the five groups, there are two cards from group A (01), one from group B (2), two from group C (45), none from group D, and one from group E (9). Thus, we must have group D=P, allowing the magician to deduce P=D={6,7}, Q=E={8,9}, R=A={0,1}, S=B={2,3}, T=C={4,5} (the same group assignment that the assistant used).
• Out of groups Q and R, the only missing card is the 8 from group Q. Thus, we must have an even permutation, and an even rightmost element. We know the rightmost element is in group P, and the even element of group P is 6; thus we can call the rightmost card as a 6, and turn it face up to get 0492?5??16.
• The numbers in the reduced list must be the three face-down cards (378, by elimination), plus whichever face-up cards are in group S or the smaller element of group T (the face-up cards of 234, i.e. 24). So the reduced list must be 42???. Seen as a cyclic list, this has three adjacent face-down cards, so the card in the middle of them must be in group S or T; the only possibility is 3, so the magician calls the second face-down card as a 3, and turns it face-up to give 0492?53?16.
• There are only two permutations left: 0492753816 and 0492853716. The former is an even permutation, the latter an odd permutation. The magician knows, from the fact that the 8 was face-down earlier, that the desired permutation is even, so 0492753816 is the only possibility; as such, the 7 and 8 can both be called and turned face-up.

Answer 2

With a bit of extra help from assistant:

A simple solution would be to simply put 4 cards face down so they form increasing/decreasing sequence. At least one of these will be always possible. Now simply tell if the sequence is increasing or decreasing by something.

Otherwise EDITED:

I was a complete moron and put wrong numbers to the formula and calculated for 6 missing cards instead of 4. The second term is the same in both cases so I missed that, and the formula seemed reasonable enough. Fixed this time, 10!/4! = positions of 6 numbered cards; times 10!/(6!*4!) = number of combinations you can select 4 out of 10, is indeed greater than 10! = all possible permutations. So this is possible by amount of data you have and need. Alternative formula I found out later is a tiny bit simpler. We have 4! missing combinations to figure out and as data we are selecting 4 cards out of 10, giving 10!/6!*4! combinations we can figure out vs 4! that are unknowns. It can be easily seen both give the same results. Anyway, even 5 missing cards are possible to figure out (which is what tipped me off that I screwed up somewhere). It fails at 6 though.

But HOW is another matter. We have ~8x as much info as needed so we can even discard some of it to not make some too arcane formula. Unfortunately, requiring just increasing/decreasing sequence is not possible, as this is just 2 sequences out of 24 (but this works when we add this 1b = x2 data from "mysteriously communicate if sequence is increasing or decreasing"). So we need something more complex unfortunately.

Now just for fun:

The formula gives that you can figure out 2 missing cards out of 3. Which you can easily do by selecting 2 sequential cards in increasing numbers with wrap around (= 1>0, 2>1, 0>2). For guesses you then simply put those numbers in increasing order from left to right. So for example: 021, flip 01; for 210 you flip 20 and for 012 you flip either 01 or 12. This wrap around thingy might be a possible way to solution even for 4 out of 10, as we would end up with 4 possible combinations (ABCD, BCDA, CDAB, DABC) encoded in a way. Sure, losing 6x (~2.6b) of information, but still good enough.

Answer 3

This does not work in various cases.

1. Find an ascending sequence of 4 cards that includes the 0th card. If it exists, flip those 4. If not
2. Find a descending sequence of 4 cards that excludes the 0th card and includes the 9th card. If it exists, flip them. If not
3. Find an ascending sequence of 4 cards that includes the 1st card and excludes the 0th and 9th cards. If it exists, flip it. If not
4. Find a descending sequence of 4 cards that includes the 8th card, and excludes the 0th, 1st, and 9th cards. Etc.

For example: [4, 9, 8, 1, 3, 2, 6, 0, 5, 7] and [8, 1, 3, 5, 9, 4, 6, 7, 0, 2] fail with this method. It is somewhat rare, so if you're doing it randomly, it would be likely to pass.

Of all 3,628,800 possible permutations 3,256,873 work and 371,927 fail, so your odds are about 90%

Answer 4

Presented without proof:

Your assistant covers up four cards that are either an increasing or decreasing sequence. If the sum of the cards that are covered is even, then it is increasing, otherwise it is decreasing. Simply observe which 4 cards are not shown in the 6, then flip them over in order while naming them.

Supporting statement:

For any ordering of 10 distinct integers, there are two sets such that the following are true: $$A = \{a, b, c, d\}$$
$$B = \{e, f, g, h\}$$
$$|A \cap B| = 3$$
$$a < b < c < d \text{ and } e < f < g < h$$
$$\text{or}$$
$$a > b > c > d \text{ and } e > f > g > h$$
$$\sum{A} = 2n+1 \text{ and } \sum{B} = 2m$$

Answer 5

To just answer the question of whether such a strategy is possible, use this corollary of Hall's Marriage Theorem.

Given a bipartite graph with parts A and B, such that every vertex in A has the same order, every vertex in B has the same order. If |B| >= |A|, then there is a matching that uses every vertex in A. If |A| > |B|, there is no matching that covers every vertex in A.

The problem effectively asks for a matching with A = { permutations of $u$ + $d$ cards }, and B = { permutations of $u$ faceup cards and $d$ facedown cards, with facedown cards being indistinguishable }

$|A| = (u+d)!$

$|B| = $ (num. ways to choose positions of faceup cards) * (num. ways to choose ranks of faceup cards) * (num. ways to order those face ranks)
= $uC(u+d) * uC(u+d) * u!$
= $((u+d)!/(u! d!)) * ((u+d)!/(u! d!)) * (u!)$

$|A| <= |B|$ iff $(u+d)! <= ((u+d)!^2) / (u! d!^2)$ iff
$u! d!^2 <= (u+d)!$

And since $720 * 24 * 24 <= 3628800$, such a strategy is possible.

Answer 6

Rambling words

I'm not sure on the proof, but I think it is possible. Since you only need to know 3 of the 4 cards, and you know which 4 are turned over, it is simply a matter of communicating 3 and inferring the 4th.

Insufficient Rules:

The highest showing card is the "indicator" card. This card will create 2 sides: a short side and a long side. Any card flipped on the short side of the indicator is the highest card flipped. If more than one, the furthest from the indicator is the highest and they will descend in value to the indicator card. If none are flipped on the short side, the closest to the indicator is the highest flipped and the furthest is the lowest flipped. Then the card nearest the lowest card is the next lowest card.

I haven't tested this at work with any kind of program, and I am certain that the rules I have are not adequate, but I think it's possible because the assistant can choose which cards. There just needs to be a less limiting rule that allows for more info.

Test case:

Shuffle: 4 | 7 | 0 | 1 | 9 | 6 | 2 | 3 | 8 | 5

Assistant chooses:

Well, the first 10 random numbers I used cannot generate a solution using my rule set. It feels really close, but I just don't know how to communicate more information.

Answer 7

I have an idea that might work but I'm actually not sure. The number of ways the assistant can flip cards is 210 so the assistant is able to communicate a number from 0 to 209 to the magician for example. The assistant then just takes the number the volunteer made and does it modulo 210. The resulting number he communicates to the magician. Now I think there is a great chance that only 1 of the 24 possible permutations of the flipped cards would make that calculation be correct so this is how the magician knows it. But it also all depends on how this number from 0 to 209 is determined based on which cards are flipped

Answer 8

Well I'm very late to the party, but a bit confused by the accepted answer, after all I gave up math for magic (or something like that). My faster to calculate? easier to remember? solution would be:

note: T1 etc. refers to the 4 turned positions (from left to right) P1 etc. refers to the actual 10 position (from left to right) O1 etc. refers to the 5 positions with an odd card (from left to right) E1 etc. refers to the 5 positions with an even card (from left to right)

My decisions:

If 1 odd number is missing (similar for 1 even missing)
- T1 is odd
- T3 is middle-even
- if P1 turned T2 is high-even
- if P2 odd T2 is high-even
- else T2 is low even

If 2 odds are missing
if the first open value is odd (similar for even)
- T4 is high odd
- T3 is low odd
- if the last odd number was not a turned T2 is high-even
- else T2 is low-even

If the missing cards are all odd or all even: fire the apprentice

The preparation of the apprentice:

if P1 and P2 are both odd: (similar for both even)
- Pick 3 even cards in either descending or ascending order
- Pick P1 if ascending, P2 if descending

else if two of {P1,P2,P3} are both odd: (similar for two even)
- Try to pick 3 from {E2,E3,E4,E5} in either descending or ascending order
- if ascending, pick P1 if odd else pick P3
- if descending, pick P2 if odd else pick P3
- if unsuccessful
- pick 01 + 02
- if O1<O2, pick E5 + min(E3,E4), else pick E2 + max(E3,E4)

I guess I have not proved that 3 descending or ascending numbers can always be chosen from 5,
nor that if you cannot do that from 4 the middle 2 must be the extremes, but I leave that "as an exercise for the reader"

Answer 9

I think That the magician can do it easily By:

Coded responses
Before I start calling out which card is which number.
We (me & the assistant) make a somewhat comedy conversation that the audience will enjoy without noticing that the assistant is actually telling me their order. A certain word can mean 1, another can mean 2, a third can mean 3 etc..
Or if you want it to be less obvious...
you can use coded Q&As
For Example you ask, Are we ready?
The assistant replays saying yes for 1, yes we are for 2, yup for 3, ok for 4 etc... and the same for the rest of the questions..

There is another method:

And it's used a lot by magician, the supposed volunteer is actually one of the staff and you all agree on a certain order

And lastly:

using the space of the table and a striped overlay (45 strips):
If there is no strips between two cards then the one to the left is zero
If there is just one strip then the one to the left is one and etc....

Note:

I don't know if this is the intended answer, but I think that they are all valid

Answer 10

When I've done things like this what I did to encode information was control the card itself. And yes, it can be done for all cases.

1) Use a back that's not symetrical, put half in one group and half in the other. Either odds/evens or first-5/2nd-five (I'll assume first 5). Now you have two distinct groups of 5. The two groups totally ignore each other and each doesn't exist as far as the other is concerned. So if the sequence is 2 9 8 3 then the "3" is considered to the right of the "2".

2) When the assistant flips the card over, she puts it above, below, or equal to the line of play. If the card is above the line of play that means the card to it's right is the highest value card. If the card is below the line of play then it's the lowest value card. If the card is equal to the line of play then it's the middle.

3) Both the board and the cards "wrap". So the card to the right of the rightmost card is the first card on the left.

Example (ignoring cards not in the group):

1 4 2 5 3
The assistant flips over the 2 (above the line of play pointing out the 5) and the 3 (below the line of play pointing out the 1).
Since you can always figure out two cards, the 3rd is obvious.