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

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

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

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