20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can the assistant see all cards? $\endgroup$ – arminb May 30 '17 at 10:43
  • $\begingroup$ so 24 possibilities? = You ask assistant question: Are you ready? Yes/Sure/Yep/We are = 4 possibilities, Now i know first card, so I say what that is: Assistant - Yes it is/ Yes it is 7th/And 7th it is - Now you know second one… etc, like that? $\endgroup$ – Jan Ivan May 30 '17 at 10:47
  • 3
    $\begingroup$ I assume this is purely a mathematical puzzle and that customised responses from the assistant are not allowed. Perhaps you can change the puzzle to something like "Step 3.5 Assistant leaves the room" and "Step 4 Magician announces each card herself before she flips it over". This eliminates those possibilities where the assistant encodes information in his responses to the magician. $\endgroup$ – Trenin May 30 '17 at 12:43
  • 6
    $\begingroup$ It is certainly possible; I found a solution using a simple greedy algorithm. I suspect that there is a huge space of possible solutions, so the real trick is to find one with enough structure to be memorized. $\endgroup$ – 2012rcampion May 31 '17 at 2:50
  • 1
    $\begingroup$ @Wen1now I editted the question to eliminate the possibility of communication between the assistant. I assume this is what you intend to make the problem strictly mathematical. If not, please revert. $\endgroup$ – Trenin May 31 '17 at 13:33
21
$\begingroup$

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. 0492753816019275384601297538460123759846012345987601234568790123456789 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.

$\endgroup$
  • $\begingroup$ This strategy seems to work, but it's a bit late and I can't concentrate properly (sorry). If it hasn't been refuted by tomorrow I'll accept :) $\endgroup$ – Wen1now Jun 2 '17 at 12:56
  • 1
    $\begingroup$ This strategy sounds really good and has all the right elements. $\endgroup$ – Ian MacDonald Jun 2 '17 at 13:18
  • 2
    $\begingroup$ I am working on coding this up, but it will have to wait until monday... It is not trivial to grok, but almost there. $\endgroup$ – Trenin Jun 2 '17 at 19:27
  • 2
    $\begingroup$ Coded it up - works for all permutations. Great job!!! $\endgroup$ – Trenin Jun 5 '17 at 13:42
  • 1
    $\begingroup$ Bravo! Fantastic solution and write up. $\endgroup$ – Forklift Jun 5 '17 at 15:09
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The second part of your answer would mean that the Fitch Cheney trick wouldn't work. $\endgroup$ – Deusovi May 30 '17 at 11:41
  • $\begingroup$ @Deusovi Nope, that trick has just the right amount of info. 4! because of the ordering of the cards you pass back, *2 because you can pass either card of the doubled suit as the first one. You can figure out 48 cards with this info and there are exactly 48 of them not in your hand. Here, you don't have this - what you see on the table is the amount of information you get, and the amount is lacking. $\endgroup$ – Zizy Archer May 30 '17 at 13:39
  • $\begingroup$ Not quite - which cards are flipped over is additional information. The assistant gets to pick those. $\endgroup$ – Deusovi May 30 '17 at 13:46
  • $\begingroup$ a simple wave to the audience as he/she leaves the stage would specify ascending or descending order--which isn't communication with the magician, but the audience. $\endgroup$ – Mike Jun 1 '17 at 17:49
1
$\begingroup$

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%

$\endgroup$
  • $\begingroup$ Yeah, that was my idea as well. Do you have any idea how to prove it works? $\endgroup$ – Wen1now May 31 '17 at 4:15
  • $\begingroup$ I was going to try brute force. $\endgroup$ – Dr Xorile May 31 '17 at 5:22
  • $\begingroup$ Oh, this doesn't work. I'll leave it up as a warning, and edit the issue. $\endgroup$ – Dr Xorile May 31 '17 at 5:54
  • $\begingroup$ Uh, why would those 2 fail? For 1st sequence, take rule 2 and flip 9832. For the second, take rule 3 and flip 1356. $\endgroup$ – Zizy Archer May 31 '17 at 7:39
  • 1
    $\begingroup$ I wrote a program that simply uses parity. Even means the cards are in order, odd means in reverse order. It has a 99% success rate - only 22,428 sets of cards have no solution. $\endgroup$ – Trenin May 31 '17 at 13:28
1
$\begingroup$

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$$

$\endgroup$
  • 4
    $\begingroup$ I already wrote a program for this exact scenario. turns out there are 22,428 combinations which have no solution. I put this in a comment to Dr. Xorile's answer. $\endgroup$ – Trenin May 31 '17 at 14:48
  • $\begingroup$ I am trying to see now if there are combinations which have multiple solutions which if the second solution is taken, it means something different. $\endgroup$ – Trenin May 31 '17 at 14:50
  • $\begingroup$ Would there be a way to communicate these special exception sets and somehow have that be part of the solution? $\endgroup$ – Forklift May 31 '17 at 14:52
  • 1
    $\begingroup$ @Trenin Just for my own piece of mind that you're right (I'm not saying you're definitely wrong), can you provide one of those combinations that fails? My strategy is slightly different than the one suggested by Dr. Xorile. $\endgroup$ – Ian MacDonald May 31 '17 at 14:57
  • $\begingroup$ @IanMacDonald My strategy is also different that Dr. Xoile. His was using 4 distinct patterns; mine simply uses parity of the positions of the cards. 9627308145 is one that fails for me. $\endgroup$ – Trenin May 31 '17 at 16:42
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you give an example of a shuffling with the cards that the assistant flips over and then the deduction of the magician? $\endgroup$ – Trenin May 30 '17 at 14:19
  • $\begingroup$ @Trenin, since I was lucky enough to find a breaking test case on my first try, I will say that my solution is deeply lacking :) $\endgroup$ – Forklift May 30 '17 at 14:40
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "The resulting number he communicates to the magician." How does he communicate this? $\endgroup$ – Trenin May 30 '17 at 17:47
  • $\begingroup$ @Trenin by choosing which cards​ to flip. As I said there are 210 ways to pick 4 card out of 10. So by agreeing beforehand what combinations stand for which number he can give this info $\endgroup$ – Ivo Beckers May 30 '17 at 17:50
  • $\begingroup$ I just realized I read the puzzle wrong. I thought 4 cards were shown and 6 were hidden. Now I understand your answer. $\endgroup$ – Trenin May 30 '17 at 17:51
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's supposed to have a mathematical solution. $\endgroup$ – Nautilus Jun 1 '17 at 21:25
  • $\begingroup$ In fairness to Sherlock, the question was edited after the fact to preclude this answer. $\endgroup$ – Trenin Jun 5 '17 at 11:52
-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm assuming the "zero" is the high value (i.e. 10) and not the low value for grouping here. $\endgroup$ – Dark Matter May 31 '17 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.