Two Plus Two Newer Archives  

Go Back   Two Plus Two Newer Archives > Other Topics > Science, Math, and Philosophy
FAQ Community Calendar Today's Posts Search

 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
  #1  
Old 11-19-2007, 04:53 PM
bigpooch bigpooch is offline
Senior Member
 
Join Date: Sep 2003
Location: Hong Kong
Posts: 1,330
Default For \"math people\": \"TRICK\" and information in one number

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? ]
Reply With Quote
 


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 11:23 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.