Magician's hide and seek with 8 cards

Question

This question is a followup to this question by @Wen1now.

After demonstrating the previous trick, the magician decided to make things a bit harder, discarding some cards so that only eight were left. The trick was much the same as before:

• The assistant started by calling up an audience member. In order to make the trick as impressive as possible, the magician and assistant wanted to be able to call up anyone and have the trick still work; as such, their strategy needed to work even if the audience member knew their strategy and actively worked against them (whilst staying within the rules of the trick).
• The following parts of the trick were done with the magician unable to see (or otherwise gain information about) what was going on:
  • The audience member was given 8 cards, numbered from 0 to 7 inclusive. They were asked to arrange them in a single line on the table (so that each of the eight cards was placed in a different one of eight predetermined positions, but the audience member had a free choice of which card went where; in other words, they were choosing a permutation of the cards).
  • The assistant selected four of the cards, turning them face down.
• The magician came back, and purely based on the 8 cards that could be seen (the identities and positions of the four face up cards, and the positions of the four face down), identified what the four face down cards must be.

Once the trick started, there was no communication, even indirectly, between the magician and assistant, except via the selection of cards to turn face down. (For example, the cards were symmetrical; there was no way to transmit information based on their orientation.) However, the magician and assistant could talk freely before the trick started, and had agreed a strategy: the assistant would select cards to turn face-down in such a way that the magician would uniquely be able to reconstruct the original permutation knowing only the identities and positions of the four face up cards. In other words, this is a purely mathematical trick, rather than involving sleight of hand or anything like that.

(Here's an equivalent formulation for the mathematicians and computer scientists out there: write a function whose input is a permutation of the list [0, 1, 2, 3, 4, 5, 6, 7], and whose output is equal to the input except that four of the elements are replaced with "?", such that different inputs map to different outputs.)

There's one other restriction that the magician and assistant were working under: they wouldn't be able to take pages of notes with them when performing the trick, so whatever their strategies were, they would have to be simple enough to memorise; listing a separate strategy for each of the 40320 possible inputs isn't a reasonable answer here.

What strategy could the magician and assistant have used?

Answer 1

The following is a simple strategy for performing the trick. In my opinion, it should be easy enough to memorize.

Core idea

The integers [0,7] can be divided into four independent pairs where the exclusive-or of each pair produces the same value. By using a strategy that preserves enough information about these pairs and the result of the exclusive-or, the permutation can be encoded and decoded.

Strategy

Note: For purposes of this strategy, first and last refer to leftmost and rightmost, respectively. The layout positions is treated referred to as if there is a natural left-to-right orientation.

Encoding the layout

The assistant does the following:

• Calculate the key value by performing an xor of the face values of the first two cards in the layout.
• Identify the three remaining pairs within the other six cards that produce the same key value for the xor operation on their face values.
• Locate the pair that begins furthest to the right (i.e. its first card is the rightmost of all the first cards for all pairs).
• If the face value of the first card of the located pair is greater than that of the second, then flip the first card the of layout. Note that this is first card of the whole layout, not the pair. Otherwise, flip the second card of the layout.
• Flip both cards of the pair used in the preceding step.
• Calculate the xor of the key value with the face value of the rightmost face-up card. Flip the card that has the corresponding face value.

Example:

• Layout: 3 7 6 2 5 0 1 4
• Key value is: 3 ^ 7 = 4
• Pairs where xor is 4: (3,7), (6,2), (5,1), (0,4).
• Identify (0,4) the pair whose first card is the rightmost of all the pair first cards.
• First card 0 is less than second card 4; flip the second card in the layout: 3 ? 6 2 5 0 1 4
• Flip preceding pair (0, 4): 3 ? 6 2 5 ? 1 ?
• Rightmost face-up card is 1; 1 ^ 4 = 5, so flip 5: 3 ? 6 2 ? ? 1 ?

Decoding the layout

The magician does the following:

• Determine the key value by performing xor on the face values of the second and third face-up cards.
• Calculate the xor of the key value with the face value of the rightmost face-up card. The result is the face value of the second face-down card.
• The first two cards are a face-up/face-down pair. The face value of the flipped card is the result of xor between the key value and the face value of the other card.
• The two remaining face values belong to the leftmost face-down cards. If the first card of the layout is face-down, the greater of those values belongs to the first card of that pair; otherwise, to the second card.

Example:

• Layout: 3 ? 6 2 ? ? 1 ?
• Key value is xor of second and third face-up cards: 6 ^ 2 = 4
• Xor key value with rightmost face-up card for second face-down card: 4 ^ 1 = 5: 3 ? 6 2 (5) ? 1 ?
• Xor key value with face-up card in first two cards to get the face-down card: 4 ^ 3 = 7: 3 (7) 6 2 (5) ? 1 ?
• The two unidentified cards are 0 and 4, since the first card of the layout is face-up, the greater value is the right card of the remaining pair: 3 (7) 6 2 (5) (0) 1 (4)
• Amaze the audience with your ability to identify the face-down cards and take a bow.

Details

Note: If someone would like to edit this to provide the concept in more formal mathematical language, feel free. That is not my forte.

This solution leverages the fact that if you exclusive-or two values [0,7] the remaining six values contain three independent pairs of numbers that produce the same result.

After calculating the xor of the first two cards, we know there are three equivalent pairs in the remaining six cards. There are 15 possible combinations of pairs.

With the remaining six, we use simple rules to flip three of them so the pairs may be identified. By flipping the pair with the rightmost initial card and selecting an initial card from another pair, we ensure that the pair flipped is to the right of the other card flipped. By selecting the other card as the one matching the rightmost face-up card after the first step, we ensure that the two leftmost face-up cards are a pair.

This allows us to identify the pairs in the final six cards as the first two face-up cards, the last two face-down cards, and the remaining pair. Since one pair remains facing up, the result of the xor operation is preserved. But information about the face-down pair is lost.

We will select the fourth card from the first two in the layout. Since the value of the xor operation is preserved in the final six cards, it doesn't matter which one is flipped. So the card selected for flipping encodes the orientation of the pair that has two face-down cards.

This preserves all the information needed to produce the original permutation in a hopefully memorable form.

Validating the strategy

The following are Python 2.7 implementations of the encoding and decoding as well as tests to verify them.

Encoding implementation and test

#!/usr/bin/python2.7

def encode(p):
    layout = list(p)

    # Calculate the key value by performing an xor of the face values of the
    # first two cards in the layout.
    key = p[0] ^ p[1]

    # Identify the three remaining pairs within the other six cards that
    # produce the same key value for the xor operation on their face values.
    from itertools import combinations
    pairs = filter(lambda (a,b): key==p[a]^p[b], combinations(range(8), 2))

    # Locate the pair that begins furthest to the right (i.e. its first card
    # is the rightmost of all the first cards for all pairs).
    rightmost_pair = max(pairs, max(pairs, key=min))

    i_first, i_second = min(rightmost_pair), max(rightmost_pair)

    # If the face value of the first card of the located pair is greater than
    # that of the second, then flip the first card the of layout. Note that
    # this is first card of the whole layout, not the pair. Otherwise, flip
    # the second card of the layout.
    if p[i_first] > p[i_second]:
        layout[0] = '?'
    else:
        layout[1] = '?'

    # Flip both cards of the pair used in the preceding step.
    layout[i_first] = layout[i_second] = '?'

    # Calculate the xor of the key value with the face value of the rightmost
    # face-up card. Flip the card that has the corresponding face value.
    for rightmost_faceup in reversed(layout):
        if rightmost_faceup != '?':  # Continue while cards facedown
            break

    layout[layout.index(key ^ rightmost_faceup)] = '?'

    # Return encoded layout
    return tuple(layout)


# Iterate through all permuatations and validate encodings
from itertools import permutations
encodings = set()
for p in permutations(range(8)):
    e = encode(p)

    # Encoded elements must either match permutation elements or be a '?'
    assert all(ex==px or ex=='?' for px, ex in zip(p, e))

    # Four '?' required for valid encoding
    assert e.count('?') == 4

    encodings.add(e)

# Ensure unique encoding for each permutation
print "Unique encodings: %d" % len(encodings)
assert len(encodings) == 40320

Decoding implementation and test

Requires the encode() function from above.

def decode(e):
    layout = list(e)

    # Find indices of face-up and face-down cards as a convenience
    i_up = []
    i_down = []
    for i, ex in enumerate(e):
        if ex == '?':
            i_down.append(i)
        else:
            i_up.append(i)

    # Determine the key value by performing xor on the face values of the
    # second and third face-up cards.
    key = e[i_up[1]] ^ e[i_up[2]]

    # Calculate the xor of the key value with the face value of the rightmost
    # face-up card. The result is the face value of the second face-down card.
    layout[i_down[1]] = key ^ e[i_up[3]]

    # The first two cards are a face-up/face-down pair. The face value of the
    # flipped card is the result of xor between the key value and the face
    # value of the other card.
    layout[i_down[0]] = key ^ e[i_up[0]]


    # The two remaining face values belong to the leftmost face-down cards. If
    # the first card of the layout is face-down, the greater of those values
    # belongs to the first card of that pair; otherwise, to the second card.
    remaining = set(range(8)) - set(layout)

    if i_down[0] == 0:
        layout[i_down[2]], layout[i_down[3]] = max(remaining), min(remaining)
    else:
        layout[i_down[2]], layout[i_down[3]] = min(remaining), max(remaining)

    # Return the decoded layout
    return tuple(layout)

# Test round-trip for all permutations
for p in permutations(range(8)):
    assert p == decode(encode(p))

Answer 2

EDIT: simple solution for flipping 3 of 5 added, see below. Not started looking for the 4 from 7 yet, although we know it exists!

I really like D Krueger's flip 4 from 8 solution, and it inspires me to try to generalize! :D

If we can flip m out of n cards, then we can flip m out of n' for all n'>n, by the strategy of simply ignoring all but n cards.

So a question is: for a given m, what's the smallest value of n which works?

We can't flip 2 of 2. But we can flip 2 of 3:
-> Flip two cards where the left one is smaller, except:
-> (1) Where there is no such pair, i.e. 321 flip to x2x
-> (2) For 123, where any two cards can be flipped, don't flip to x2x

We can't flip 3 of 4, by the pigeonhole principle:
There are 4! = 24 permutations of 4 cards.
There are only C(4,3)*4 = 16 displays that might greet the magician, who cannot therefore disambiguate in all cases.

Can we flip 3 of 5?
There are 5! = 120 permutations of 5 cards.
There are C(5,3)*5!/3! = 200 displays.

Can we match the perms 1-1 against a subset of the displays? The relevant maths is Hall's Marriage Theorem. Suppose we have m pigeons and n holes, and a relation "likes". Is there a pigeon-pleasing assignment of pigeons to holes where each bird gets a hole that it likes, with no two sharing the same hole? Obviously if we can find a subset of k pigeons which between them are only interested in less than k holes, then we can't make these pigeons all happy. The theorem says that this condition is not just necessary but sufficient. If there is no such unhappy subset, then a pigeon-pleasing assignment must exist. Note that the result is "non-constructive" - it does not tell us which pigeon goes where!

In the flipping 3 from 5 case, every perm can transform into 10 displays. But each display comes from at most 6 perms. So if we have k perms, then they map onto at least k*10/6 > k displays. So no unhappy subset can exist!

This approach can be applied to all m, and says that if the number of perms is less than the number of displays, then a magician's mapping must exist. (Presumably this general argument is a known corollary of Hall's Theorem when applied to (a,b)-regular bipartite graphs.) But this cool result tells us nothing about how to build such a mapping, let alone one which is easy for the magician and assistant to remember.

We can't flip 4 of 6:
There are 6! = 720 permutations of 6 cards.
There are only C(6,4)*6!/4! = 450 displays.

We can somehow flip 4 of 7:
There are 7! = 5040 permutations.
There are C(7,4)*7!/4! = 7350 displays.

Now, how to flip 3 from 5? Here's one way:

1. Regard the 5 cards as forming a circle. If there are three increasing in succession clockwise, then flip them. [15 out of 24 circles are handled here.]
2. If that can't be done, then regard the 5 cards as forming a pentagram, and again if there are three increasing in succession clockwise, flip them. [Note that these three will not be adjacent in a circle, so we can always distinguish between case 1 and case 2.] [6 out of 9 possible pentagrams are handled here.]
3. If we still haven't succeeded, then there are only three pentagrams possible:
   4 1 0 3 2
   4 3 0 2 1
   4 2 0 3 1
   However, it turns out that if we flip in step 2, then the two unflipped cards can never be 2a. [Check the 6 possible cases.] So in the three remaining cases, we flip to leave 2a:
   4 x x x 2
   x x x 2 1
   x 2 0 x x
   Since the value of a is different in each of these three exceptional cases, we can always identify the missing x's uniquely although now the flipped cards don't form a rising sequence. Easy for the conjuror to remember that the pentagram pattern for these is always 4 p 0 q r, where q>r, so just a question of slotting the 2 into the right slot.

I haven't hunted for an algorithm to flip 4 of 7, I just know that it exists! But it might not be easy enough for the magician to remember.

This does mean that we could post a sequence in OEIS (Online Encyclopaedia of Integer Sequences): of the minimum viable number of cards (n) for any number of flips (m):

m: 0 1 2 3 4 5  6  7  8  9 10 11 12 13 14...  
n: 0 1 3 5 7 9 12 15 18 22 26 30 34 39 44...  

Thanks for your time!

Answer 3

First, can this be done?

The Magician is facing 24 possible outcomes (4! or 4x3x2x1), not 8!. He can see what cards are left, he knows where they are. It's reasonable for a human to memorize 24 outcomes, especially for their professional skill.

So "case 0" could mean "Left to Right we have the smallest remaining card, then 2nd smallest, then 3rd, then 4th" (1st, 2nd, 3rd, 4th), while "case 1" could mean (1st, 2nd, 4th, 3rd) and "case 23" could mean (4th, 3rd, 2nd, 1st). So the Mage's job is pretty easy assuming the assistant can send him which case it is.

Although the Magician's assistant can flip over any of 8 cards followed by any of the 7, her boss doesn't know what order she did things so it needs to be the raw value of the cards.

My first thought was using the first 6 cards as bits in a register, so you can indicate a numbers from 0 to 31, but since you must flip at least 2 of those cards and can only flip at most 4, the number of numbers you can indicate is actually only 18. Instead what we do is designate the cards themselves to represent powers of two. So the Ace is 2^1, the two is 2^2, the three is 2^3 and so forth. Yes, this means some values are excluded, for example you can't create the number zero because you need to flip 4 cards, but presumably you don't use that number in your scheme.

This gives us 70 situations (8*7*6*5 / 4!) that the assistant can indicate. Note while being able to figure out what message she's sending is easy (it's just adding together 4 powers of 2), jumping from what number she's sent to which case it is might be a problem. She sent a 15... which case is that? However we've still got only 70 inputs resulting in 24 outputs, so I'm going to call that within human reach.

The nasty problem is she now has to look at the cards, figure out which case she can create and indicate by flipping cards. I.e. it does NO good to indicate "case 0" if the only way to create the number(s) indicating that involve flipping cards which have to stay down.

I think we're in the area of raw computational ability here, i.e. she looks at the first set of 70 positions she can create, sees what number that creates, understands what case that indicates, and then checks to see if it is actually true. There's a 1-in-24 chance it works, and if so she can stop there. If not then she has to do the next one, and so forth.

I'm not sure if this is always doable or not (70 instances of 1/24 suggests 95% of the time it will work, maybe we can structure things so it always will), but imho we're past the point where humans can do this in any reasonable amount of time.

So I don't think it can be done... but I'd love to be proven wrong on this.

Answer 4

Now that the puzzle's been solved by someone else, I thought I'd post my own answer, as it works on a completely different principle to the "winning" answer.

Assistant's strategy

We'll letter the cards from A to H, left to right and wrapping round, so that card 0 is always card A, the card to its right is card B, and so on. Start by turning cards A and B face down (i.e. the 0 and the card to its right).

Check to see whether the original permutation was odd (i.e. requires an odd number of swaps to get into order) or even (i.e. requires an even number of swaps to get into order); incidentally, this is always consistent, because there's no way to make any odd number of swaps on a permutation to get it back to its original order. If it was odd, turn card C face down. If it was even, turn card D face down.

Finally, consider cards B, E, F, and G, plus whichever of cards C and D is face down. Currently, two of those cards are face down. Consider the cards sorted into numerical order. If the two face-down cards are adjacent in the order (or top and bottom, i.e. we wrap round the end of the list for "adjacent"), turn the (only) card that isn't adjacent to either face down. Alternatively, if the face-down cards are not adjacent, turn the (only) card that's adjacent to both face down.

Now we have four face-down cards, so it's the magician's turn.

Magician's strategy

The first task is to identify which letter belongs to which card. If there are three or four face-down cards in a row (including wrapping around the end), this is trivial; the first of those must be card A (because H is always face-up and only two of D, E, F, G can be face-down, the row of three must involve C, meaning A and B to its left are also face-down). If there are only two face-down cards in a row, it's also trivial; they must be A and B in that order. The only other possibility is to have two runs of two face-down cards, in which case they must be A,B,D,E (for A,B to form a run of two implies that C is face up and thus D is face down); luckily, that can't be rotated onto itself, so we can always uniquely identify which run contains A. We can now call card A as a 0 and turn it face up.

With three face-down cards, we can identify which numbers they have (but not which one has which) by elimination. This lets us identify the numbers that B, (face down from C or D), E, F, G have, so we can sort that list of numbers to produce the same list that the assistant was working with. Two of the face-down numbers will be adjacent to one other number in the list (potentially wrapping from start to end); the third will be adjacent to both or neither. This third number must belong to card E, F, or G (whichever is face down). Call it and turn it face up.

Finally, there are two face-down cards, and we know (by which of cards C and D was face down) whether we're dealing with an odd or even permutation. That's enough information to tell which is which (because if we got them the wrong way round, the permutation's parity would be wrong as the two possibilities are one swap away). So we can call them and turn them face up.

Example

Let's start with 3 7 6 2 5 0 1 4, the example used in the winning answer.

The assistant reasons as follows:

Mentally label the cards: 3D 7E 6F 2G 5H 0A 1B 4C

Turn A and B face down: 3D 7E 6F 2G 5H -A -B 4C

Check whether the permutation is odd or even. One example sequence of swaps is 37625014 → 07625314 → 01625374 → 01265374 → 01235674 → 01234675 → 01234576 → 01234567, i.e. 7 swaps, so this is an odd permutation.

Because it's an odd permutation, turn C face down: 3D 7E 6F 2G 5H -A -B -C

Cards BCEFG are numbered 14762, or when sorted, 12467. The face-down cards are 1 and 4, i.e. -2-67. The 2 is adjacent to two face-down cards, so we turn that face down.

The final list of cards is 3D 7E 6F -G 5H -A -B -C, i.e. 3 7 6 - 5 - - - (because the letters only exist in the assistant's mind, they aren't actually on the cards).

So the magician turns up and sees 3 7 6 - 5 - - -. Here's the magician's reasoning:

There are three cards face-down in a row. The leftmost must be card A, so we letter the cards (again, mentally) as 3D 7E 6F -G 5H -A -B -C.

Card A is 0 (always), so we can call that one: 3D 7E 6F -G 5H 0A -B -C.

By elimination, cards BCEFG must be (in some order) 76124. Sorting that gives us 12467. The face-down cards here are 124; the 1 and 4 are each adjacent to one other such card (even wrapping round the ends), the 2 is adjacent to two. So the 2 must belong to card E, F, or G; it obviously isn't E or F because they're face up, so we can call card G as 2 and turn it face up to give 3D 7E 6F 2G 5H 0A -B -C.

The remaining cards are 1 and 4. We know (because card C is face down) that we're dealing with an odd permutation. 37625041 is even and 37625014 is odd, so the solution must be 37625041. The magician calls the last two cards, turns them face up, and walks off to thunderous applause.