[4973] in cryptography@c2.net mail archive
Re: Bridge
daemon@ATHENA.MIT.EDU (Matt Crawford)
Fri Jun 25 16:19:21 1999
To: "Ge' Weijers" <ge@progressive-systems.com>
Cc: "Arnold G. Reinhold" <reinhold@world.std.com>, cryptography@c2.net,
coderpunks@toad.com
From: "Matt Crawford" <crawdad@fnal.gov>
In-reply-to: Your message of Fri, 25 Jun 1999 11:08:04 EDT.
<19990625110804.D25998@progressive-systems.com>
Date: Fri, 25 Jun 1999 10:43:21 -0500
> > > > > There are 52! bridge hands, so a random hand has
> > > > > log2(56!) = 226 bits of entropy or 68 decimal digits worth.
> >
> > No, just 52! / (13!)^4 hands, which is around 2^96.
>
> The interesting part is to come up with an algorithm that only uses 96 bits.
I can do it in 101 bits trivially. Start with deck in a fixed order,
use two random bits per card to decide which hand gets that card. If
the selected hand is full, give the card to the next unfilled hand
clockwise. That's 100 bits for the first 50 cards. The 51st card
needs at most one bit and the 52nd needs none.
Shaving off the last five bits, hmm ... I can save at least 0.4 bits
on the 50th card ...
Matt
