Introduction

In this lab, you will write some programs to discover secrets behind a card trick.  The card trick is neat because it illustrates many of the fundamental concepts in discrete math.  You will need to discover the appropriate data structures for your explorations and programs.

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.

(Note that your discrete math text has a small section on generating permutations in numerical order, and you can feel free to use that if you wish.  It describes a function that takes a permutation and generates the next one in order.  There is also a problem on the Cantor expansion of a number, which gives a direct 1-1 function between integers and permutations.)

Program 2.  Write a program that simulates the trick for 28 cards.  Your program needs to play both parts of the trick. 
    a.  Given a set of 5 cards from {1, 2, … 28}, the program should construct an ordered set of four cards.    (Note:  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).  For example, given {2, 4, 6, 8, 10}, your program might 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 (10, 12, 1, 7) you would calculate that is permutation number 17 and therefore, the missing number is the 17th of the unseen 24 cards.   The unseen cards are: (2,3,4,5,6,8,9,11,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28).  The 17th card in this list is 21.  Your program should return 21.

Our Working Strategy

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 Challenge

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.

Can we make a strategy that works for more than 52 cards?

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.

Extending Our Working Strategy to Other Cases

1. 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.
2. Same question for 3 cards?  2 cards?
3. 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?
4. 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.

Extending Our Combinatorial Arguments to Other Cases

5. The upper bound for n = 5 is 124 cards.  What are the upper bounds for n = 2, 3, 4?
6. Write a formula for the upper bound in terms of n.

Counting the Huge Number of Possible Strategies

7. 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 choice of permutation of n-1 cards for each of the possible sets of n cards in the contestant’s hand.  (For n=5, this equals 120^225150024).

Constructing New and Better Strategies

A table is a strategy whenever 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, consider n=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 for n=3 and a deck size of 8, there are 6⁵⁶ tables to try.  With the same assumptions, this would only take about 1.1958 * 10²⁵ centuries.

Working with Simpler Cases to Avoid the Combinatorial Explosion

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 with n=3, and deck sizes of 6, 7, and 8.

For n=3, our working strategy can be used to fill a table for a 6-card deck, as calculated in problem 2 above.  Use two suits and 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.

Exercise.  If we try to use our working strategy for a deck of 7 cards, verify that the strategy is unsuccessful.  Fill in the table for 7 cards successfully yourself by hand.

Program 4-5.  Write a program using depth first search that searches for a strategy for 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).  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, may take a very long time.   In fact, I want you to see your program hang up in the large search space, so you should pick a bad ordering to start.  Nobody knows what makes one ordering backtrack and another sail through.  We do know that there are orderings that luckily succeed in finding a strategy, without ever having to backtrack at all.  That means they take 56 steps rather than the worst case 6⁵⁶ steps!  

Here is one such ordering.  For every set {a, b, c} in the table generate the possible sets of pairs in this order:  (ba, ab, ca, ac, cb, bc).  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.  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).

An Intuitive Method to Achieve the Upper Bound

In class, we will teach you an intuitive and efficiently computable method to do the trick with the maximum number of cards.  The trick uses modulo arithemtic and permutations.  For n=3 and an 8 card deck, it produces a different strategy than the one in the table computed by program 5.  The neat thing is program 4-5 will not work for the 5 card case because 124 choose 5 is too big an array to fill out and store.  The only way to make a strategy for the 5 card trick is, given 5 cards, to calculate "on the fly" which ordered 4 cards to use.  You cannot fill out the choices for all sets of 5 cards in advance.

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.