Friday bridge math puzzle!
Mood: tired
Posted on 2007-01-19 08:19:00
Tags: bridge math
Words: 763

onefishclappin forwarded me this fascinating puzzle yesterday, and I thought "Ooh, I should figure this out", then started thinking about it, then went back to work for about 5 seconds, then gave up and worked it out (roughly). Here it is:


After you've dealt out a hand, are there more different legal ways to play out the hand, or more ways to bid the hand?

Here, only legal plays and bids are counted, so no bids or plays out of turn, insufficient bids, revokes, etc. Other than that, the plays or bids don't have to make any particular bridge sense, they just have to be legal.

There are few things I like better than a good combinatorics puzzle. Here's the analysis I sent her, along with some better numbers: (don't read if you want to try it yourself!)

My gut instinct was that there were more ways to play out the hand, so let's look at that first. It depends what the hands are (since you have to follow suit), but there are at most 13!^4 ways to do this, and you can achieve this is each player is dealt a full suit of cards (each player can play their cards in any order). The least number of ways would be if each person got a 4-3-3-3 distribution, and is something like (13!/(4!*3!*3!*3!))*(3!^4)^4 ((13!/(4!*3!*3!*3!) for the order the suits are played in, 3!^4 for the order of cards in a suit for each person, and the ^4 for all 4 suits). That's just an estimate, though: 13!^4 is definitely an upper bound.

The number of ways to bid is a little more tricky. If you're not familiar, there are 35 "normal" bids (1-7 in clubs, diamonds, hearts, spades, and notrump) and the bids have to be in ascending order (or pass). If the other team bid, you can double, which means that they can then redouble, both of which are cancelled when a new "normal" bid is made. The bidding is ended by three passes.

My first analysis said that there are 2^35 choices for which bids are made along the way, and there are around 10 ways for transitioning from bid to bid (number of passes and doubles & redoubles), so that would give (2*10)^35. This isn't quite right, though: firstly there are 21 ways to transition between bids (see below for a list). More importantly, it's really the sum from i=0 to 35 of 4*(35 C i)*21^(i-1)*7, where i is the number of "normal" bids that are made (4 for number of passes at the beginning, 7 is the number of ways to go from the last bid to the end of the bidding). I think that's right (although the i=0 case is wrong; it should be 1, since the only way to have 0 bids is four passes). So, this is 1 + 28 * sum from i=1 to 35 of (35 C i)*21^(i-1). Hmm, not sure off the top of my head to simplify this, but a quick script to compute this gives 128745650347030683120231926111609371363122697557 (1.287*10^47), which is the answer that the sender of the email got and the answer found elsewhere too. So I got lucky that my initial estimate was fairly wrong in concept, it ends up being close to the same! (20^35 is 3.44*10^45)

And 13!^4 is "only" 1.5*10^39, so the answer is that there are one million times as many ways to bid a hand than to play it (and really, more than that for most usual hands). Fascinating problem - thanks onefishclappin!

List of bid transitions: this is the list of the 21 ways to get from one bid (B1) to the next bid (B2) while keeping the auction alive. p=pass, D=double, R=redouble. It took a few minutes to get these right!
B1 B2
B1 p B2
B1 p p B2
B1 D B2
B1 D p B2
B1 D p p B2
B1 p p D B2
B1 p p D p B2
B1 p p D p p B2
B1 D R B2
B1 D R p B2
B1 D R p p B2
B1 D p p R B2
B1 D p p R p B2
B1 D p p R p p B2
B1 p p D R B2
B1 p p D R p B2
B1 p p D R p p B2
B1 p p D p p R B2
B1 p p D p p R p B2
B1 p p D p p R p p B2

Update: a nice simplification of the number of auctions that doesn't require a script!

5 comments

Comment from tehfanboi:
2007-01-19T13:12:19+00:00
Honestly I always find your ability to solve and get excited about these math problems fairly interesting even if I don't follow the math terribly well (Liberal arts, stopped taking math because I was very confused by calculus). I kinda wish you had a YouTube video where you explained how and why you chose to do the things you do since then you could make photoshopped visual aids to help explain to the math endereducated like myself! :)

Comment from destroyerj:
2007-01-19T13:42:27+00:00
I wouldn't have thought of that myself, but that's what YouTube has been powerful for, from what I've read :). Well, 2 things I guess, the forwarding around of funny clips of existing stuff, and also the easy sharing of things like this in a communication medium that's much stronger than text. I support the request for Professor Greg Math Busters videos!

Comment from gregstoll:
2007-01-19T23:15:34+00:00
Thanks! I'd always get excited about problems as a kid, which is why I always thought I'd grow up to be a mathematician. But I really really like combinatorics and some of the more advanced stuff not so much.

And, neat idea. Maybe if I had a whiteboard... :-)

Comment from medryn:
2007-01-19T14:09:36+00:00
Not that it really matters, but wouldn't 4*13!^4 be a better upper bound, since there are 4 ways to pick who goes first? Or are those not considered different?

Comment from gregstoll:
2007-01-19T23:02:46+00:00
Depends on your interpretation of the problem. I'm gonna say no because who gets to go first is determined by the bidding, but really it could go either way...

This backup was done by LJBackup.