Stonehill College

Data Structures and Discrete Mathematics Learning Community

Professor Shai Simonson

Combinatorics and Data Structures Laboratory

A Combinatorial Card Trick

Introduction

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 1.  Write a program that helps the magician and accomplice encode and decode n! permutations.  Your program should give an option to (D)ecode or (E)ncode.  For encoding, the input is two integers m and n, and the output is the mth permutation of the elements {1, 2, …, n}.   For decoding, the input is n and a permutation p, and the output is m, where p is the mth permutation of n elements.  Your 1-1 correspondence between permutations and integers should be in numerical (lexicographic) order.  It will be very helpful to have a "next permutation" generator method.  The method takes a permutation and generates the next one in numerical order.  For example, 1234 becomes 1243.  And, 2314 becomes 2341.  Here is a link that explains how to code the "next permutation" method, and how to call the method m-1 times in a loop in order to find the mth permutation.

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.  Encoding:  Given a set of 5 cards from {1, 2, … 28}, provided by the user,  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.  Decoding:  Given an ordered set of four cards from the set {1, 2, …, 28}, provided by the user,  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).

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

Lower Bounds on the Number of Cards Possible – Based on Our Working Strategy
  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

Upper Bounds on the Number of Cards – Based on a Combinatorial Idea
  1. The upper bound for n = 5 is 124 cards.  What are the upper bounds for n = 2, 3, 4?
  2. Write a formula for the upper bound U in terms of n.
  3. 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.

Counting the Huge Number of Possible Strategies

Now let’s analyze the possibility of other strategies.  In practice, a strategy needs to be easily decodable, but theoretically a strategy is no more or less than a list of what the accomplice should do in every possible situation.
  1. 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:

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 10450000000 centuries to try all possible tables.  Even for n = 3 and a deck size of 8, there are 656 tables to try.  With the same assumptions, this would only take about 1.1958 * 1025 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.  Recall that in problem 2 you calculated that for  n = 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.

 For example, given the triple 123, there are two odd numbers.  Ralph will show 1-2, where the 1 indicates the odd suit, and the 2 is the single permutation of one digit.  Shai would add one odd card to 1, getting 3 as the missing card.  Notice that when there are three cards all of the same suit, then Ralph has more than one option in what pairs to display, and I should be able to decode any of them.  This reveals why the working strategy is not very efficient.  In an optimal strategy, (which could work for up to 8 cards), Ralph's decision would be unique.
Program/Exercise 3. 
a.  Write a program to fill in the table of 20 (6 choose 3) slots (123, 124, 125, ... , 456)  for six numbers using 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, may take 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 656 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).
Programs 4-5.  Try your program with ordering (ba, ab, ca, ac, cb, bc), and print out the results for n = 3 and an 8 card deck. Try some other orderings like (ba, ab, ca, ac, bc, cb), and report your results. Try to find other orderings that succeed, and others that fail (or take too long to succeed).  Compare the strategies for each success to see if they are different.

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

// Here you can increment a global counter to keep track of the extent of the backtracking
//  You can kill your program if the counter goes over 10,000,000
// And then you can print out the array that you filled up until then.

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 a set of 6 pairs that does not backtrack and once for one that does backtrack.  In your report, you should try and report some additional orders.  There are 6! = 720 orders in all.  You should print a solution if an ordering succeeds in a reasonable amount of time, else you can stop your program and save your machine from burning up.  For every set that succeeds, you should print how many times you needed to try a new pair in order to find a solution.  For no backtracking, this is just 56.  For backtracking, it will range from 56 to 6^56.  You can kill your program if the backtracking counter exceeds some huge number, say  10,000,000, and you can dump the current array when you do.

A Practical, Intuitive, and Efficiently Computable Method to Achieve the Upper Bound

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.  For n=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, given n cards, calculates "on the fly" which ordered n -1 cards to use. 
Program 6.  Write a program to implement the intuitive practical method for n = 3, and print out the resulting 56 entry table. 

Program 7.  Write a program that implements this intuitive method for n = 5 and 124 cards.  You should not try to print out the whole huge table!    It is impossible! 
                  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.

Enrichment:  If we have time, we will watch this film called Proof, with Gwyneth Paltrow and Anthony Hopkins, about the human side of proof and being a mathematician. 
 


Back to LC homepage