For "math people": "TRICK" and information in one number

[bigpooch]

I was thinking about generalizing a "neat trick" when having
difficulty getting to sleep:

NEAT TRICK
==========

Here is an interesting "calculating" trick if you have an
ordinary deck just missing one card. Suppose you could
only see the deck one card at a time for a few seconds and
then go to the next one until the 51st card. Sure, some of
you might be able to remember all the cards and determine
the missing ticket, but not everyone is like Stu Ungar. So
if you have a bad memory, how do you identify the missing
card?

The simple idea is to have two sums; one for ranks and one
for suits. For example, for ranks, use 1 for ace, 2 for
deuce, ...12 for queen and 0 for king. Also, it turns out
the sum can be reduced modulo 13, so the "rank sum" could
be between 0 and 12. For suits, you could use -1 for
clubs, 0 for diamonds, 1 for hearts and 2 for spades.
Again, you could reduce everything modulo 13. Then the
missing card can easily be determined: if you had the
entire deck, the total rank sum is equivalent to 0 (mod 13)
and the total suit sum is equivalent to 0 (mod 13).
[Just take the "negative" (modulo 13) of the sums to
determine the identity of the missing card. ]

The above idea is equivalent to denoting each card by a
unique integer between 0 and 51 inclusive, so you could use
modulo 52, but it's much easier in practice to break it
down to a "rank sum" and a "suit sum". Now instead of
memorizing cards, you only need to add and remember a few
numbers.


TWO CARDS
=========

Instead, suppose the deck had TWO missing cards. Now, it's
not so trivial to assign integers to cards and besides, not
many humans would be able to add large numbers quickly (AND
make the proper assignment to cards). A computer scientist
could tell you it can be done by just assigning 2^k for k=0
to 51, but we want to be more efficient.

The idea is again to assign numbers to cards and go through
the deck one card at a time and keep adding numbers so at
the end, you have enough information in the sum to identify
the two missing cards.

Instead of 52 cards, we could have n items where n could be
much larger, but suppose we have the resources to just hold
a very big number and add another big number precisely.


QUESTION
========

What is the assignment of numbers to cards (where the
numbers are nonnegative integers) minimizing the largest
number assigned to a card, so that the "sum of the deck" is
minimized and there is enough information in the sum to
identify the two missing cards?


m MISSING CARDS (m >= 3)
===============

It's also not a big step to see that this can also be done
for three or more missing cards and the general solution
should be easy for the mathematicians that read this. Also,
out of curiosity, what is the largest number assigned for
n=52 and each m between 3 and 10 inclusive (THIS, I don't
know, but just know the relevant recurrence equations and
haven't bothered finding the roots for m >=3) ?

[ Anyone find this easy? ]

[hitch1978]

Would you call this an expansion on binary code?

[Siegmund]

The number of possible combinations of m missing cards is 52 choose m. There exist numbering schemes that could, in theory, result in a number between 1 and 52 choose m. Most of them would be fiendishly hard to remember. Ways that give sums between 1 and 52^m would be easier to create.

The trick of remembering two numbers 1-13 and 1-4 runs into trouble with more than one card -- you might be in the position of being able to name two ranks and two suits, but not sure if the two cards are [img]/images/graemlins/heart.gif[/img]7 and [img]/images/graemlins/club.gif[/img]8, or [img]/images/graemlins/club.gif[/img]7 and [img]/images/graemlins/heart.gif[/img]8.

If I were going to do this trick, I would find a prime P>m and a number k<p such that 1^k, 2^k, 3^k, ... (p-1)^k mod p are distinct numbers, and keep track of two or three sums mod P.

If, however, you ask me to identify four or more cards, rather than memorizing four values to associate with every card in the deck (or calculating 37^5 mod 53 in my head!), I will either directly keep track of the 52 cards in my head, or I will start out by remembering 8191,8191,8191,8191, and deducting 2^(rank-1) from the (suit)th number as I go.

I personally would find it easier to learn to count all the cards in the deck than I would to do the subtraction, but non-card-players might find the numbers easier.

[bigpooch]

Clearly:
[ QUOTE ]

The trick of remembering two numbers 1-13 and 1-4 runs into trouble with more than one card


[/ QUOTE ]

The idea for two cards using one number is simply identify
them by:

0,1,(1+0)+1=2,(2+1)+1=4,(4+2)+1=7,(7+4)+1=12, etc.

You can identify these as Fibonacci numbers less 1, i.e.,
F(2)-1, F(3)-1, ..., F(n+1)-1. [Alternatively, you can
find the recurrence relation to get the same result.]
These numbers are big, but the biggest is less than 2^51.
[Note: F[n] is the closest integer to rho^n/(sqrt(5) where
rho is [1+sqrt(5)]/2 < 2. ]


For more than two cards, the recurrence relation is little
more complicated for m>=3. In general, the relation is

r^m - r^(m-1) - r(m-2) -... - r -1 = 0.

The largest root d[m] for the mth recurrence will be
between d[m-1] and 2.