About a year and a half ago, I wrote a blog post about counting bridge auctions. In the intervening time, pretty much every blog post I've written has been an answer to a question on fivethirtyeight's 'The Riddler'. This week's Riddler Classic is about counting bridge auctions!
The question is:
The question is:
From Mark Whelan, shuffle up and deal. And count very, very high:
Bridge, that venerable card game, begins with an auction. There are four players around a table, each sitting across from his or her partner. At its simplest, the auction goes like this: Beginning with the dealer and orbiting around the table, players can place a bid or pass. Players who’ve passed can re-enter the bidding later. A bid is comprised of a number (one through seven) and a suit. Every legal bid must be higher than the one that came before, meaning either that its number is higher or that its number is the same and its suit is higher (from high to low, the suits go no-trump, spades, hearts, diamonds, clubs).
The auction ends if the other three players pass after a bid, or if all four players pass right away.
How many different legal bridge auctions are there?
Note that this question ignores doubles and redoubles (they are 'extra credit' for the riddler). So I haven't actually answered it in my original blog post. However, I did show my working, so it's very easy to adapt the answer. In the 'full' case, there were 28 auctions that ended with the final contract being 1♣, because any of the four players could open 1♣ and then there are 7 ways for an auction to get to 3 passes after doubles and redoubles, and then for every auctions that ended in 1♣, there were 22 auctions that ended in 1♦ (Because you can replace any of the final three passes in any auction with 1♦, and then have 7 ways to finish, or you can replace the 1♣ bid with 1♦). This is probably explained better in the original post.
Now, things are much simpler. There are only 4 possible auctions that end in 1♣ (anyone can open 1♣, and then everyone else has to pass). For each of these, there are 4 auctions that end in 1♦ (replace any of the final 4 bids with 1♦, and then everyone has to pass, and so on. So with 35 bids available, the total number of auctions in this situation is 'just':
4 +4^2 + 4^3 + ... + 4^35)
= 4*(1 + 4 + ... + 4^34)
= 4*(1-4^35)/(1-4)
= 393,530,540,239,137,101,141
or roughly 4*10^20
Compare this to the 'full' case:
Now, things are much simpler. There are only 4 possible auctions that end in 1♣ (anyone can open 1♣, and then everyone else has to pass). For each of these, there are 4 auctions that end in 1♦ (replace any of the final 4 bids with 1♦, and then everyone has to pass, and so on. So with 35 bids available, the total number of auctions in this situation is 'just':
4 +4^2 + 4^3 + ... + 4^35)
= 4*(1 + 4 + ... + 4^34)
= 4*(1-4^35)/(1-4)
= 393,530,540,239,137,101,141
or roughly 4*10^20
Compare this to the 'full' case:
28 + 28*22 + 28*22*22 + 28*22*22*22 + .... + 28*22^34
= 28*(1 + 22 + ... + 22^34)
= 28*(1-22^25)/(1-22)
= 128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,556
In case you don't feel like counting the digits, that's approximately 1.29*10^47.
Last time, we went on to determine a bidding system where we could determine which player had which card based entirely on the auction (and with each player knowing what bid they had to make at each stage). This time, that isn't possible.
We hinted at this last time (you can try the naive system where the player with the ♣2 bids 1♣, the player with the ♣3 bids 1♦, etc., but this only manages to let you place 35 cards, so you definitely need the doubles and redoubles), and now we can see why - there are 'only' ~5*10^28 deals, so without using the doubles and redoubles, there aren't enough auctions for it to even be possible to place every card (regardless of the issue of whether everyone knows which bid to make at which point.
We hinted at this last time (you can try the naive system where the player with the ♣2 bids 1♣, the player with the ♣3 bids 1♦, etc., but this only manages to let you place 35 cards, so you definitely need the doubles and redoubles), and now we can see why - there are 'only' ~5*10^28 deals, so without using the doubles and redoubles, there aren't enough auctions for it to even be possible to place every card (regardless of the issue of whether everyone knows which bid to make at which point.
RSS Feed