mathematics - Magician's hide and seek with 8 cards

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

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

Blog

Tuesday, January 24, 2017