**************************************

I know of the five card trick you mention, and I have seen a solution which
extends the trick to include the possibility of a joker in the deck. You
can do this with numbers 1-53 as well, simply assigning them to cards, since
you pretty much do this anyway with the card trick.

Basic solution (if no joker appears among the numbers chosen):
Since there are five cards and only four suits, two of them must be of the
same suit. Choose one of these to be the hidden card, choosing the one which
is (cyclically) 6 or fewer cards above the other. For instance, if you had
the queen and 3 of a suit, you would hide the 3 since it is the fourth card
above the queen (king, ace, 2, 3). Place the other card of the same suit as
the first card. Place the other three cards in a permutation (relative to
their sorted order, based on some assignment of numbers 1-53 to cards) to
indicate whether the hidden card is one, two, three, four, five, or six
ranks above the first card. Since a card that is seven above another card is
six below it, you can always choose one of the two cards that is six or
fewer above the other.

When the joker is chosen:
If there are two cards of the same suit, hide the joker and choose one of
these two cards of the same suit to be the first card. Arrange the other
three cards so as to indicate that the hidden card is the other card of the
same suit. The presence of the clued card among the last three cards shown
indicates that the actual hidden card is the joker.
If the other four cards are of different suits, pick two of these cards
which differ in rank by 0 to 5 ranks to be the hidden card and the first
card, and place the joker among the last three cards. The presence of the
joker indicates that we're using a slightly different convention than
normal; the permutations now indicate 0-5 instead of 1-6 ranks above the
first card, and the hidden card is of the fourth suit rather than the suit
of the first card. The 0-5 convention is necessary to account for the
possibility that the cards are the joker plus four-of-a-kind. If they are
all of different ranks you can always choose two that are 5 or fewer apart,
and if two or more are the same, you can always choose a pair.

I seem to recall there being a version of this that worked for two
distinguishable jokers. If both jokers come up, then you put one as the
first card to indicate that the second joker is hidden. If you get a joker
and four different-suited cards, proceed as above. I don't know how you
distinguish between the two jokers when you get one of them and four other
cards which are not all of different suits, though.

There is also a more purely mathematical system which does not depend on
suits, and I seemed to remember it being named somebody's Wheel, but I could
not find anything about it.

I searched for five cards choose four order on groups.google.com and found
several threads in rec.puzzles related to this. In one of these from 1997
(Subject: PUZZLE: Playing-Card Communication), Seth Breidbart asks what is
the largest number of cards for which this would work, and Wei-Hwa Huang
notes that 124 is an upper bound, and Jim Yingst then suggests a method
which works for 124:

Jim writes:
Assign the cards values 1-124 (if that hasn't already been done). Given
five such cards, randomly selected, arrange them in ascending order, total
their value, divide by five and take the remainder. Use that remainder to
determine which card to hide: for 1, hide the first card, for 4, the
fourth, and for 0, the fifth. By looking only at the remaining four
cards, it it possible to identify a group of exactly 24 other cards which
might have been the hidden card. For example, if the cards are (7, 8, 24,
89) then the hidden card must be one of (3, 10, 15, 20, 26, 31, 36, 41,
46, 51, 56, 61, 66, 71, 76, 81, 86, 92, 97, 102, 107, 112, 117, 122). Use
the order of the four unhidden cards to specify which of the 24 (= 4!)
possibilities it is.

Note that the 24 possible cards for a given set of four revealed cards
(where N is the modulo 5 sum of the four revealed cards) are the 5k+N cards
less than the lowest displayed card, the 5k+N+1 between the two lowest
displayed cards, the 5k+N+2 between the middle two displayed cards, the
5k+N+3 between the two highest displayed cards, and the 5k+N+4 more than the
highest displayed card. The 24 possible cards are one of five possible
sequences of every 5th card among the 120 cards which are not shown; the sum
of the values of the cards shown tells you which one. This is actually
simple enough that it the two participants could actually do the
calculations in their head reasonably quickly, quickly enough for actually
performing the trick.

Later in this thread, various people mention that this puzzle/trick came up
there (on rec.puzzles) in 1996 and 1994, which sounds right, because I
remember it coming up once back when I still read the group regularly. There
was also a variation of this as a Ponder This! puzzle about a year ago.
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/October2000.h
tml In the variation, you have to arrange five numbers to clue a sixth,
different number -- but you don't get to choose which number is to be clued.
You do, however, have the option of hiding one of the five numbers you are
given and only showing the other four.

Joseph DeVincentis

**************************************

Ed,

I found this on the sci.logic group.
It appears that max=124, but asks for a "simple" strategy.

Another search with "Ilias Hungarian algorithm" on sci.logic shows an algorithm based on Hall's Theorem on bipartite matching ("marriage problem") that could be used to implement the 124 case.

Lew Baxter
---------------

The following was written by Eric Farmer in sci.math explaining a
matching
problem with the four-of-five card trick. The last question is somewhat
tough.
Any input would be helpful.

There is an assistant, an audience and a magician. The audience
picks five cards. The assistant is able to select which card to place
face
down, and the magician has only the order and value of the cards to work

with. For a 52-card deck, at least one easily remembered strategy for
performing the 5-card trick is known.

We can generalize: from a deck of n cards, the audience selects m cards.

The assistant arranges k of the selected cards, and upon viewing this
arrangement, the magician names the remaining m-k cards. For what n>m>k
is
this possible?

The key observation is that the trick is possible if and only if each of
the
possible m-subsets of cards can be arranged so that no two arrangements
are
identical in the first k cards (why?). Certainly, then, we must have
P(n,k)
= C(n,m), where P(n,k)=n!/(n-k)! and C(n,m)=n!/(m! (n-m)!). In other
words, there must EXIST at least as many k-arrangements as m-subsets.

A more interesting problem is proving that this obvious necessary
condition
is also sufficient (it is). This yields an answer to the second
question: the largest n for which P(n,4) >= C(n,5) is n = 124, so the
trick
could in principle be performed with a 124-card deck!

Now I have a question: is there a simple described strategy for
performing
such a trick for general (valid) n, m, and k? (or just for n=124, m=5,
and k=4?)

Eric Farmer

**************************************

To do better than n=24 obviously you encode some information in what
numbers you choose, rather than simply using the 24 permutations. The
easiest way to handle n=52 is to use your choice of 4 number to convey a
parity bit, saying "the missing number is one of the 24 low (24
high) numbers of the 48 remaining." There are any number of properties you
might use to do that.

The theoretical maximum which cannot be exceeded is n=124. The audience
selects one of n-choose-5 problems to pose, and the magician writes one of
n-permute-4 clues on the chalkboard; these nC5<nP4 for all n<124, equal
for n=124, greater for all n>124.

The only complication the magician faces is making sure that his mapping
from the nP4 clues onto the nC5 sets is such that the clue is a subset of
the target set. This is possible, combinatorically. I don't however see a
simple enough way to make this map for it do be doable in your head in a
few seconds.

Extending the trick to n=76 or n=100 is easier than n=124 - the easiest
way now is to use the choice of clue members to convey which tertile or
quartile the missing number is and use the permutation method to pinpoint
it within a block of 24.

Gordon Bower

**************************************

I am responding to your "Can you help?" question concerning the Five Card
Trick. Having volunteered, I must admit that I am still working on a
solution to the original problem and see why increasing n complicates
matters considerably.

It is clear that the 24 permutations are usable no matter which of the five
cards is dropped. Or to put it the other way, we are not using our choice
of dropped card to convey information. I have been looking for a function
from (distinct) 4-tuples to {0,1} with the property that for any 5-tuple
there is at least one 4-tuple subset that maps to 0 and another that maps
to 1. This would provide the missing one bit of information to get to 48
possibilities. I am racking up quite a collection of mappings that almost
work.

I am probably way behind other respondents to your question who have almost
certainly solved the original problem. I suspect that 52 may be a firm
bound because the only remaining information (aside from the 24
permutations) comes in the form of the choice of dropped card and because we
have to look at the worst, not average case, but I am not close to a proof
of that fact. I will start on that once I have solved the current problem.

I wanted to say that I am a great fan of your website (I initially found it
via the link from www.gamepuzzles.com <http://www.gamepuzzles.com> ). I
also wanted to say that I recently received The Mathematical Explorer as a
birthday present and have been having fun with it (nothing to share yet).

Please let me know if the search for a solution for n >52 or an
impossibility proof leads to any joint efforts (such as exhausting a class
of functions). In general let me know if there is any way I can help.

Thanks,

Lyman Hurd

**************************************

Ed,

Obviously, the theoretical maximum number of combinations is 24 permutations
x 5 = 120.
And seems like the optimal solution does exist!
It's quite difficult for me to explain it, though... The first part is easy:

(1) How to chose the number to hide:

Let's suppose we've got sorted sequence of numbers A[0], A[1], A[2], A[3],
A[4].

k = (A[0]+...+A[4]) mod 5

We have to hide number A[k]

(2) How to find the hidden number by the given four numbers B[0], B[1],
B[2], B[3] (sorted):

...

...I tried to describe this part but it was too confusing and I deleted
that. I'll try to formulate the solution clearly it in the next couple of
days.

Igor Krivokon

**************************************

Hi,

The solution I figured out a couple years ago runs like this.
There are M = n! + n-1 cards (numbered, say, from 1 to M).
Someone chooses n of those card somehow.
You turn one of those n cards face-down and arrange the other (n-1)
cards in some order.
Your confederate looks at the values and order of the n-1 cards and
identifies the face-down card.

M is the largest value for which this can work, because number of ways
of choosing n distinct (unordered) elements from M is the same as the
number of ways of choosing n-1 distinct ordered elements from M. For
values larger then M, there are not enough orderings of n-1 elements,
and for smaller values, there are extra orderings of n-1 elements.

I pick the face-down card by adding the n numbers (mod n). If the value
is 1 (mod n), I choose the smallest card; if it is 2, I take the 2nd
smallest card, and so on. For a given set of (n-1) face-up cards, there
are (n-1)! possible face-down cards that will give the proper ordinal
relation. Pick your favorite listing of the (n-1)! permutations of the
face-up cards to identify which of those (n-1)! cards is actually the
face-down card.

-jim

**************************************

**************************************