In this lab, you will write some programs to discover mathematical secrets behind a card trick. The card trick is neat because it illustrates many of the fundamental concepts in combinatorics and discrete math. You will also need to discover the appropriate data structures for your explorations and programs. More than just card trick, however, this lab touches on the general problem of experimentally predicting the time complexity of a depth first search backtracking algorithm, when a mathematical prediction is too difficult. It also touches on the relationship between graph theory, combinatorics, and programming.

In class, Ralph and I performed the following trick for the class. A magician asks someone from the audience to choose five cards randomly from a standard deck. The person does not show these cards to the magician, but does show them to the magician’s accomplice. The magician’s accomplice then looks at these cards, and shows four of them in a particular order to the magician, who then immediately identifies the last card, which remains hidden in the audience.

At first thought the trick seems impossible, because there are only 4! = 24 ways to order four cards, and 24 pieces of information is not enough to identify a unique value among the possible 48 remaining cards (four are showing). However, a more careful analysis reveals that the accomplice has more than 24 choices up his sleeve. The accomplice may choose which four cards to show, as well as their order. There are C(5,4) = 5 ways of choosing four cards from five, and 24 ways to order each, hence the accomplice has 120 different choices of information he can send. The hard part is that the magician cannot easily decode this information and thereby determine the corresponding missing card.

She can easily decode 24 pieces of information by just examining the permutation of the four visible cards. We could agree in advance on a numbering of the 24 permutations. For example, the permutations could be ordered 1234, 1243, 1324, 1342, etc in so-called lexicographic (like alphabetic but for numbers) order. The cards would each be thought of as a number from 1 to 52. The ordering of the four cards say 3, 7, 51, 43 would correspond to the permutation 1243 and hence the number 2.

Using just this simple encoding/decoding scheme, the trick could only be done with 28 cards. The magician and accomplice simply communicate a number from 1 to 24 using the ordering of the four cards. There are four cards showing, so this number identifies which of the remaining 24 cards is hidden.

**Program 2.** Write a program that simulates the trick
for 28 cards. Since the magician's assistant can see 4 cards
out of the 28, the magician needs only communicate to the
assistant which of the 24 remaining cards is he secret card.

a. Given a set of 5 cards from {1, 2, …
28}, the program should construct an ordered set of four
cards. Your program will need to choose which
set of four cards to order. A simple way is to discard the
lowest card and order the remaining four cards. The
discarded card can be at most 24, so the shown permutation can
identify it. For example, given {2, 4, 6, 8, 10}, your
program would return (4, 6, 10, 8) which is the second permutation
indicating that it is the second card (number 2) of the unseen 24
cards.

b. Given an ordered set of four cards
from the set {1, 2, …, 28} the program should calculate the
missing card. For example, given the order (20, 22, 18, 19) you
would calculate that this is permutation number 17 and therefore,
the missing number is the 17th of the unseen 24 cards. Since
the magician always hides the lowest card, the 17th unseen card is
the card 17.

Your program needs to play both parts of the trick, and should
give an option to (C)onstruct the ordered 4 cards - part (a)
above, or to (R)ecover the missing card - part (b).

One method that allows the magician/accomplice to encode/decode more than the obvious 24 pieces of information, is to notice that among the five cards chosen from a standard deck of 52, there must be two of the same suit (due to the pigeonhole principle). The first card shown by the accomplice is one of these two cards, and the second is never shown. If we number the cards in a suit from 1 to 13, and wrap around if necessary, then given any two cards, there is always one which is six or less below the other (again the pigeonhole principle – if they were both 7 or more less than the other, then there needs to be 14 cards). The accomplice chooses the card that is 6 or less below the other. For example, given the 3 and the Jack, we choose the Jack.The accomplice then chooses an ordering of the last three cards to encode a number from 1 to 6. The magician decodes this number, (value 1-6) and adds it to the first card, in order to recover the identity of the missing card.

Look here for an example.

The question you must explore is whether we can do this trick with a larger deck of cards. This requires the construction of better strategies. But what exactly is a strategy?A strategy is an onto function from ordered sets of 4 cards to unordered sets of 5 cards. This means that the magician computes a set of 5 cards from an ordered collection of 4, and thereby deduces the 5th card. A strategy can be easily computable in the magician’s head for a performance, but in principle it is no more or less than looking up a value in a big table.

In the case of 52 cards, there are C(52, 4) * 4! ways to order 4 cards, and C(52, 5) ways to choose 5 unordered cards. A strategy for 52 cards is a table of length C(52, 4) * 4! containing entries from the C(52, 5) sets of 5 cards. A single dimensional array is a good enough data structure.

Note that although the decoding is unique, the encoding is not. Given a set of five cards there may be a number of ordered sets of four that the accomplice might choose, each of which of course would decode back to the original five. This is like the simple case we did before with only 28 cards. The domain of the function is larger than range, so although the function is onto, it is not 1-1. That is, the inverse is not a function.

Note that when the deck has exactly 124 cards, then C(124, 4) * 4! equals C(124, 5). Therefore, any successful function will be one-one and onto, so both the encoding and decoding would be unique.

When the number of cards becomes greater, no strategy is possible. In this case, we have more sets of 5 cards than ordered subsets of 4. Hence if a strategy were possible, then by the pigeonhole principle, there would exist two sets of five cards, for the same ordered subset of four cards. But if that is the case, then given a particular ordering of 4 cards, the magician could not possibly determine which 5-card set it corresponded to, and hence never be able to recover the hidden card.

The discouraging thing is that our working strategy seems to have no slack at all. We divide the deck into exactly four groups to guarantee the duplicate suit, and choose the first card and hidden card to get the number of possible hidden cards down to six. Then we have six pieces of information left (three ordered cards) which we can use to identify the hidden card – just enough. It seems unlikely that we could extend our strategy to work for 124 cards.Nevertheless, we will explore this possibility by considering simpler versions of the trick and writing some programs. Let’s think like engineers, and look at our boundary conditions, consider special cases, and the extreme cases.

- If we do the trick by letting the person choose 4 cards and the accomplice shows an ordered subset of three of them, then what is the maximum number of cards for which our working strategy works? Note: You should think of the deck as having three suits.
- Same question for 3 cards? 2 cards?
- Let’s go in the other direction. If we let the person choose 6 cards and the accomplice shows an ordered subset of 5, then how large a deck can our working strategy handle?
- Generalize your results above for the case where n is the
number of cards chosen, and the accomplice chooses an ordered
subset of
*n*-1.

- The upper bound for
*n*= 5 is 124 cards. What are the upper bounds for*n*= 2, 3, 4? - Write a formula for the upper bound
*U*in terms of*n*. - Write formulas for the number of ways to choose
*n*cards from*U*, and for the number of ways to order*n*-1 cards from*U*. Prove that these are equal.

- Assume we are using the largest size deck of cards
possible. Let
*n*be the number of cards chosen, where the accomplice chooses an ordered subset of*n*-1. Calculate formulas in terms of*n*, for:

- The number of ways the contestant can choose his cards.
- The number of different permutations available to the
accomplice for each of the contestant’s choices. (For
*n*= 5, there are 120 possibilities). - The number of different possible
*tables*. A*table*is a list of permutations (each length*n*-1), one permutation for each of the possible sets of*n*cards in the contestant’s hand. (For*n*= 5, this equals 120^{225150024}).

A table is astrategywhenever it contains no duplicates. If there was a duplicate then the magician would have no way to know which of the two different hidden cards to decode. Based on the numbers in problem 7, you can see how completely hopeless it is to search for a strategy by trying all possible tables. For example, considern= 5 where the deck has 124 cards. Assuming we had a super-futuristic computer that takes only 1 billionth of a second to generate a whole table and check it for duplicates, it would still take more than 10^{450000000}centuries to try all possible tables. Even forn= 3 and a deck size of 8, there are 6^{56}tables to try. With the same assumptions, this would only take about 1.1958 * 10^{25}centuries.

We are under the weight of a heavy combinatorial explosion. Nevertheless, working with smaller cases, may still shed some light on the problem. We will work withn= 3, and deck sizes of 6, 7, and 8. Forn= 3, our working strategy can be used to fill a table for a 6-card deck. Recall that in problem 2 you calculated that forn =3, our working strategy works with at most 6 cards using two suits. Assume that odd numbers (i.e. 1, 3, and 5) are one suit, and even numbers (i.e. 2, 4, and 6) are the other suit. The table starts with 123, 124, 125, and ends with ... 456. You must fill each entry with an ordered pair from the triple of that entry.

a. Write a program to fill in the table of 20 (6 choose 3) slots (123, 124, 125, ... , 456) for six numbersusing our working strategy. If you prefer, you can do this by hand.

b. If we try to use our working strategy for a deck of 7 cards, verify that the strategy is unsuccessful. (Hint: it fails after 123, 124, 125). Fill in the table for 7 cards successfully yourself by hand, using any strategy that works.

**Programs 4-5.** Write a program using depth first
search that searches for a strategy for *n = *3 and a deck
of 8 cards, until you generate a legal table.

This strategy could be printed as a cheat sheet for the magician and his accomplice. Recall that a legal strategy is a table where every ordered set appears at most once. For every set {a, b, c} you should try ordered pairs in some fixed order, say (ab, ac, bc, ba, ca, cb). For each pair in order: if it has not been used in another place in the table then use it for entry {a, b, c}. If it has been used elsewhere, then go on to the next pair.

There are 6 pairs, so there are 6! = 720 possible orderings of which (ab, ac, bc, ba, ca, cb) is only one. Design your program so that this order could be easily changed. That will make the next program easy to do.

Note, that your program, due to massive backtracking,maytake a very long time. In fact, with the ordering I suggested above, (ab, ac, bc, ba, ca, cb), you should expect to see your program hang up for hours in the large search space. Nobody knows what makes one ordering backtrack and another sail through. There may be some elegant mathematical theorem that predicts which ordering finds a clean 1-1 function, but no one has yet discovered such a theorem. Meanwhile, your program can check empirically.

It is known that there are orderings that succeed in finding a strategy, without ever having to backtrack at all. That means they take 56 steps rather than the worst case 6^{56 }steps! One such "fast" ordering is (ba, ab, ca, ac, cb, bc). Note that this ordering comes from generating the permutations of {a,b,c} in reverse alphabetical order: cba, cab, bca, bac, acb, abc, and then deleting the first character, giving the list (ba, ab, ca, ac, cb, bc).

Hints for Programs 4-5:

Here is some help for programs 4-5. The program uses a structure exactly like you use in your backtracking programs in data structures -- also known as depth first search.

A depth first search method for programs 4-5 with a structure exactly like you use in data structures for backtracking looks something like this:

Boolean findstrategy(i) // fills an array with pairs from index i through 55

if i==56 then return true; // you filled up 0 through 55 so you are done

Let xyz be the triple in slot i;

for j =1 to 6

{ Try the next ordered pair from the triple xyz; Call this a_b;

If a_b has not yet been used, then

{ assign a_b to slot i; remember that a_b has been used // Use a separate Boolean array ;

if findstrategy(i+1) return true;

// if false, then the call is backtracking and we continue in the loop to the next pair

remember that a_b is no longer being used;

}

}

return false; // you tried all 6 pairs and failed with all of them, so backtrack

You should demonstrate findstrategy(0) to me at least twice, once for each of set of 6 pairs of unordered triples - one that does not backtrack and one does not backtrack. In your report, you can report additional orders that you try, and state whether they succeed or not.

Trying to modify programs 4-5 for

n= 5 is not useful or practical. The table will be too big (C(124, 5) entries) to print, and the computation of the entries will be slower. Furthermore, it is not obvious which ordering of 4-card permutations to use to avoid backtracking. Rather than try to generalize programs 4-5, and fill in a complete chart, you will write a program that given a set of 5 cards from a deck of 124, calculates the ordered subset of 4 cards, and vice versa. This means you must figure out a way to compute the entry of a particular slot in the table efficiently in order to perform the trick with 124 cards. With your new program, you can have someone choose five numbers at random between 1 and 124, and you and your accomplice will both use the program. Your program should calculate what ordered set of four cards to show the magician. It should also work backwards, and tell the magician what is the secret (fifth) card given an ordered set of four cards.

In class, we taught you an intuitive and efficiently computable method to do the trick with the maximum number of cards. The trick uses modulo arithmetic and permutations. Forn=3 and an 8 card deck, it produces a different strategy than the one in the table computed by program 5. Unfortunately, programs 4-5 will not work for the 5-card case because 124 choose 5 is too big an array to fill out and store. That is, you cannot fill out the choices for all sets of 5 cards in advance. However, the intuitive strategy will work. The intuitive strategy, givenncards, calculates "on the fly" which orderedn-1 cards to use.

Program 7. Write a program that implements this intuitive method for

Instead, you should allow the magician and his assistant to do the trick with 124 cards by allowing two options:

a. The user inputs five numbers, and the program returns an ordered subset of four numbers.

You can do this program by looking
at the 5 cards, determining the card to be hidden. Loop
through the 124 cards and store the possible candidates in an
array (there are 24 of these, including the hidden card.
Look up the index of the hidden card in the array and find the
permutation of that index (as in program 1). Use that
permutation to order the 4 non-hidden cards. For example,
given the 5 numbers 23, 27, 59, 87, and 93. You would hide
93, and since 93 is the 18th of the possible cards that could be
hidden (see power point link below), you would exhibit the 18th
permutation of the remaining 4 numbers, namely 59, 87, 27, 23.

b. The user inputs an ordered set of
4 cards, and the program returns the missing fifth card.You can do this by looping through
the 124 cards and determining which 24 cards can be the missing
card. Store these cards in an array. Then
determine which permutation is indicated by the ordering of the
cards. Use the number of the permutation to pull out the
hidden card from the array.

**Epilogue: **There is a very elegant proof, using
Hall’s Theorem about perfect matchings on bipartite graphs,
showing that there must exist a strategy for the maximal size
deck. Unfortunately, this proof is completely
non-constructive, so it does not help us practically. You
can learn more about this proof and about the intuitive way to
actually perform the trick with 124 cards in this paper
and in this power point presentation.

Back to LC homepage