mathematics - Is this 10-card magic trick possible?

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

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.