Another week, another Riddler Express:

The optimal strategy is presumably obvious, but I guess I should get it out of the way - you should always guess higher when there are more cards higher than your current card, and you should always guess lower when there are more cards lower than your current card.

With 2 cards you are guaranteed to succeed.

With 3 cards, if the first card is a 1 or a 3 (2/3 chance), you just reduce to the 2 card case, and always succeed. If it's a 2 (1/3 chance), then you have a 50% chance of getting the first guess right, and then you're in the 2 card case. So that's 2/3 + 1/2*2/3 = 5/6 chance of success. 

Let's do 4 cards. There are effectively 2 cases (a 1 and a 4 are the same, and a 2 and a 3 are the same).
If you draw a 1, then you're in the 3 card case, and you succeed with probability 5/6. 
If you draw a 2, then there's a 2/3 chance that you get your first guess right, and after that, you either have a 100% chance of success (the next card is a 4) or a 1/2 chance (the next card is a 3, and you have to guess whether the third card is a 1 or a 4). That's 2/3*(1/2+ 1/2*1/2) = 2/3*3/4 = 1/2 chance of success.
A 3 is clearly the same as a 2, so that's
1/2 * 5/6 + 1/2 * 1/2 = 8/12, or 2/3 chance of success. 

Note that you get your first guess right fully 5/6 of the time (1/2 the time you draw a 1 or a 4, and then you get it right 2/3 of the remaining times, for 1/2 + 2/3*1/2 = 5/6), and then you're in a 3 card case, so you might intuitively think that your probability of success is 5/6 * 5/6 = 25/36, but this isn't quite right. When your first guess is right, you are less likely to be at one of the 'ends' of the deck, so your second guess is harder on average when the first guess is right. 

I can't figure out how to solve this analytically, so I went ahead and coded it up: 
https://github.com/johnfaben/riddler/tree/master/HigherOrLower

See the graph on the right for probabilities of succeeding given various numbers of cards in the initial deck. Note that for some reason the initial deck the Riddler question started with was 9 cards (2-10), so the answer would be ~0.17. The answers to the 'stretch questions are:
2-20: "~0.08%" (I printed 20 cards instead of 19 on the graph, and I can't be bothered to change it...)
2-100: "I am not running a simulation long enough to actually get any results - as close to zero as makes no difference"
How do your chances of getting to the end change? Roughly, you increase the chance of failing by 0.75 for each extra card you add (in the limit, your chances of success on the first card approaches 0.75, as you have a 50% chance if you're in the middle, a 100% chance if you're at one of the ends, and the chances change linearly between those two, and in the limit, the effect of landing in the 'wrong' half of the draw when you get the first guess right will shrink, as almost everything is 'near the middle'). So your chances of success are roughly proportional to 0.75^n. To illustrate this, I plotted 0.75^n on the graph as well (that's the blue line). 

Note that it would be relatively easy to get an exact answer for the 9 card question - there are after all less than 1 billion orders of 9 cards, so you could just work out your chances of success for each of them, but I am not going to do that, mostly because my code would require a significant rework to handle taking the permutation as an input, rather than the number of cards, but also because that wouldn't help us with the 20 card case, and because the curve above is smooth enough that I'm pretty confident the simulations are doing their job. 

 This week's Riddler Express is, inevitably, about the World Cup again. It's one of those that begs to be solved empirically (which I've done here: https://github.com/johnfaben/riddler/tree/master/Penalties), but is probably also relatively easy to solve exactly, so I'll give that a go below. ​

0Here's my first try. There are three ways for a shoot-out to end early. After three penalties, when one team is 3 ahead, after four penalties, when one team is 2 or more ahead, or after 5 penalties, when one team is 1 or more ahead. It ends after three about 0.7% of the time (one team makes all three of their 3/4 shots, and the other team misses all three, and 3*3*3/4*4*4*4*4*4 = 27/4096). 

It ends after four if one team is 2 or more ahead after the first penalty, but was not 3 ahead after the fourth. This is... wait, this is going to get tricky. Why am I bothering to consider how many penalties are actually taken?!? That will lead to some horrible conditional probabilities, and all I really care about is whether it is over after 5 penalties. 

Here's my second try. There are 6 ways for a shootout to go to sudden death. The teams score 0 each, 1 each, 2 each, 3 each, 4 each or 5 each. 

The probabilities of these outcomes are: 

0 each: 
((1/4)^5)^2 = 1/1048576 ~= 0.00001%
1 each
(5C1 *3/4*(1/4)^4)^2 = 225/1048576 ~= 0.002%
2 each: 
(5C2 * (3/4)^2 * (1/4)^3)^2 = 8100/1048576 ~= 0.77%
3 each: 
(5C3 * (3/4)^3 * (1/4)^3)^2 = 72900/1048576 ~= 6.95%
4 each: 
(5C4 * (3/4)^4 * 1/4)^2 = 164025/1048576 ~= 15.64%
5 each: 
((3/4)^5)^2 = 59049/1048576 ~= 5.63%
So the final probability is 304300/1048576, or roughly 29%. 

How does that match up with what I found with a simple simulation? 

This week's Riddler Classic is slight variation on a classic puzzle. In fact, it's a special case of the classic puzzle, but despite that, I think is probably actually harder than the original. Inspired by James Barton's 15 minutes of fame last week, I thought I'd write up my solution to this one. 

Here's the puzzle: 

How to go about this? Well, the first thing to notice that any line which goes through the centre of an individual rectangle bisects the area of that rectangle exactly. To see this, consider what happens if you rotate the rectangle through 180 degrees - the line will meet itself, and the two pieces will sit on top of one another. So not only does every line through the centre of a rectangle divide into two pieces of equal area, it actually divides it into two congruent pieces. 

So how does that help us? The key is to realise that an 'L shape' is actually two rectangles - one filled in, and one blank. It's easy to construct the sides of the 'blank' rectangle by just extending top and right hand side of the 'L' (the dotted black lines in the right hand diagram). You can then find the centres of both rectangles by drawing their diagonals (the blue and red crosses). 

Now, the line which passes through the centres of both of these rectangles bisects the area of the big rectangle and also bisects the area of the small rectangle, so it must bisect the area of the L shape as well (half of the big rectangle is equal to half of the small rectangle plus half of the L). 

Ok, nice puzzle - but what about the the classic puzzle I mentioned earlier? Well, there's no reason in this puzzle for the little rectangle and the big rectangle to be lined up so neatly. (in fact, there's not really any reason for them to be anywhere near each other). The 'classic' version of this puzzle that I've heard before is about cutting a cake with special frosting on one section, and dividing the special frosting exactly in two, for which the solution is pretty much exactly the same. 

There are some interesting extensions to this new puzzle. It's pretty clear that wherever you put the icing on an rectangular cake, and whatever shape it is, you can always divide both cake and icing exactly in two with a single straight cut (rotate the knife around the centre of the cake, it will eventually pass over the whole of the icing, so at some point it must divide it exactly in two), although you won't necessarily be able to construct this with just a straightedge. But for what other shapes of cake and icing is it possible to do this in general? And when you do need the icing to be carefully placed to allow it to work? 

As I said, I think the L shape puzzle is actually probably harder than the more general version, because the way the rectangles are arranged makes it possible to draw so many more lines - if you're given the 'tilted' version, there's basically only one thing you can try with a pencil and straightedge. With the 'L shaped' version, it's possible to go down a variety of dead ends joining up corners of the L with each other before you get to the answer. 

So, this blog post is a long story... the above is this weeks Riddler Express. I initially read that as 'three people share a birthday', and that, it turns out this is actually surprisingly tricky (certainly much harder than the actual problem... all the below is written to answer that puzzle, but don't worry, it has a happy ending...

Let's start with the 'classic' birthday problem first. In this case, there are only two options - either at least two people share the same birthday, or no-one does. The probability that no-one shares the same birthday is 1*(364/365)*(363/365)*...(365-22)/365 = (365!/342!)/365^2 = 0.4927. The first person can have any birthday, and then the second person can have any of the 364 other birthdays, and so on... 

It doesn't seem there's an equally neat solution for the case where we want three people to share a birthday. You can get a pretty good rough and ready estimate by assuming all the triples independently have a probability of 1/365^2 to share a birthday, and then counting the number of sets of three people. 

There are 23 C 3 = 23 * 22 * 21 / 3! = 1771 sets of 3 people in a group of 23 people. Assuming independence, the chances that none of them share the same birthday is thus: 

((365^2-1)/(365^2))^1771 = 0.9867

and the chances that there is some triple with the same birthday would be 0.0143 (or about 1.4%). 

However, that independence assumption is potentially quite far off - a group where three people share the same birthday is way more likely than average to have another group of three people that share the same birthday, so this actually significantly underestimates the true odds. Before we calculate the true odds, let's just have a quick visualisation of what they are (very inefficient simulation code here).

So 0.0143 probably wasn't too far off - it looks like the true odds are something like 0.013. How can we work that out exactly?

Well, if there are not 3 people with the same birthday, then either no-one shares a birthday (we already know how to work out the probability of that), or there are only pairs of people that share a birthday. 

The probability there is exactly one pair that shares a birthday is relatively straightforward. The pair can be any of the 23C2 possible pairs, they can have any one of the 365 birthdays, and then everyone else must have a different birthday, so thats: 

(23C2*365*364*...*343)/365^23 = 0.111

There doesn't seem to be a nice closed form for this, so we just work out the probabilities that there are exactly 2 pairs, exactly 3 pairs, etc, and add them together - that's what the python codes does below (it's done step by step to avoid problems with floating point precision). The probability that there are 3 or more people with the same birthday is 1 - the sum of all of these, which comes to 1-0.987 = 0.0127 (so our independence assumption wasn't too bad after all). The Riddler also asked* for the probability of 3 matches in a group of 14 people, which we can now work out is 0.00266. While we're here, we should probably answer the obvious extension question - it looks from the graph like there have to be 88 people in the room for the probability of 3 or more matches to be > 50%, and this turns out to be correct - with 87 people the probability of 3 or more sharing a birthday is 0.4995, and with 88, it's 0.511.

I played in the Scottish Winter Foursomes bridge competition in January. My team wasn't especially successful, getting knocked out just before the quarter final stage, but mostly stumbling our way into the quarter finals due to the vagaries of the draw. After the competition had finished, I sat in the pub with Jun and discussed various things. One of which, was the fact (which I remember from reading a Peter Winkler book) that there are *a lot* more auctions than deals in Contract Bridge. This is sometimes somewhat surprising to bridge players (and entirely uninteresting to non-bridge players), but it's true.

In order to understand the rest of this, you'll need to know how an auction in Contract Bridge works. I could try to write that out myself, but instead, I've stolen the section from the wikipedia page on bridge (slightly edited to remove the bits that aren't relevant).

How many auctions are there?

Let's start by counting the number of auctions where the final contract is 1♣. There are 28 of them. Any of the 4 players can open 1♣, and then there are 7 ways for the auction to finish - it can be passed out, either of the two opponents can double, and either opener or his partner can redouble. I've written out all 7 possibilities assuming the first player opens 1♣ below: ​

So how many auctions are there that end 1♦? For every auction than ends in 1♣, there are 22 that end in 1♦. Why 22? Well, you can replace any of the final three passes in any auction with 1♦, and then there are 7 different ways for it to end, as in the table above, and you also have the option of skipping the 1♣ bid entirely, and replacing it with a bid of 1♦, so that 3*7+1 = 22. There are 35 possible contracts (each of ♣, ♦, ♥, ♠, and NT at each of 7 levels). The same logic applies to all the other bids, so the total number of bridge auctions is: 

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. 

For contrast, the other obvious "big number" that appears in bridge combinatorics is the total number of possible deals. This is just 52!/(13!)^4 (if you care about vulnerability, it's a little bigger than that), or:

53,644,737,765,488,792,839,237,440,000.

It should be pretty clear that this number is a lot smaller than the number we have above, but just for confirmation, it is about 5.3*10^28. That is, there are about 2 quintillion times more auctions than their are deals. 

An auction for every deal?

Ok, so there are a lot more auctions than deals. That leads to an obvious question - is there a way of designing a bidding system such that each player always reveals their full hand in the auction? It's not completely obvious that the answer to this question is yes - there are obviously lots of surjective mappings from auctions to deals, but the feature we're looking for is that each player knows what bid to make when it's her turn, which is potentially quite a big restriction. However, it turns out that such a bidding system does exist. 

The first obvious try is this: the player with the first card (let's say the ♣2) opens 1♣. The player with the second card bids 1♦ and so on. If a player ever has multiple missing cards, they should just make the bid corresponding to the highest card they have - e.g., if you have all of the ♣2, ♣3 and ♣4 , but not the ♣5, you open 1♥. This is a promising start, but it only allows us to place 35 of the 52 cards successfully. On the other hand, we haven't even tried to use doubles and redoubles, so there's a lot of room for improvement.

As we discussed above, there are 22 different ways of getting from 1♣ to 1♦. There are 16 different ways of distributing two cards between the four players. Can you use 16 of the 22 effectively to determine the location of two different cards for each level of bidding? It turns out the answer is yes. Here's a couple of different ways of visualising this. We'll assume that North has the ♣2, and that they therefore open 1♣ (unless they also have the next two cards, in which case they skip directly to 1♦. The rest of the auction is determined by who has the next two cards.

This table is clearly a mapping from the auctions to the possible holdings - each pair of cards is associated with a different auction, and all the auctions are legal. What is not obvious from this table is that at each stage in every auction each player knows which bid to make. That is, you don't want East to have to distinguish between situations where North and South might both still have a card, and she has now way of knowing which. 

It is not obvious, but it is true. Here's a second visualisation, which hopefully makes this clear - this one is effectively a decision tree for each player at each bid. I've used the notation (EW) to mean "East has the first card and West has the second card", and I've written a brief text description of the criterion each player is using to make their bid along the arrows. You can check for any auction that at each step, each player knows what to do. 

If you follow along any path through the diagram, you can see that at each decision point, each player only has to make decisions based on the cards in her hand.

Further Reading/Sources

Everything in this post is inspired by a discussion in Peter WInker's fascinating book Bridge at the Enigma Club, which also includes discussion of cryptographic bidding systems, and several other interesting bridge-related ephemera (what's the lowest number of high card points you can give NS such that they can make 3NT double dummy? What if you also get to place the EW cards?). I can't find my copy right now, so I'm not sure how much I've blatantly stolen from Winkler, and how much of this is original, but I can say that if you liked this post, you would almost certainly enjoy reading Winkler's book. 

There are several sources online that have the calculation for the number of bridge auctions (here and here). There's also this one by Paul Kuiniewicz, which is the first hit on Google for me, has the wrong answer. This worried me for a while, but I finally figured out it's because he got the number of possible ways an auction can start wrong - you can in fact have 0, 1, 2 or 3 initial passes, and his answer is exactly 3/4 of my answer, so that's all's well with the world. 

Richard Pavlicek, who has one of the most extensive and wide-ranging bridge sites on the web has an interesting discussion of 'Mapping bridge hands to numbers' - ie, he wants a unique deal for each number between 1 and 5.3x10^28, and a relatively low-complexity way of writing down the mapping, which has a similar flavour to the problem of mapping auctions to deals, although gets to a much less intuitive answer. He doesn't appear to have the total number of auctions, although I might have missed it.

At work the other day I had to change my PIN for a certain application. It was a purely numeric PIN, and the change came with the following restrictions: 

• PIN must not contain repeated digits (e.g. 11111)
• PIN must not contain consecutive digits (e.g. 12345)

Now, I think it's pretty clear that the restriction is intended to apply to only those strings which consist entirely of repeated or consecutive digits (ie, strings that look like the examples given), so there are in fact only 10 + 7 = 17 out of 100,000 possible PIN codes being excluded by this rule, and it isn't doing too much harm. 

But what if you took it more literally? By a strict interpretation of the rules, 74583 should not be allowed, because it contains consecutive digits (45), and 38871 would not be allowed, because it contains repeated digits (88). There is some ambiguity over whether 24682 should be allowed (is the 2 in that string repeated?). If we did take the rule literally, how many combinations would we be left with? Obviously it depends on the length of the PIN - the particular PIN in question was 5 digits, but let's have a look at what happens for various different lengths, with the different rules:

As you would expect, the percentage of passwords that aren't allowed goes up as the number of digits goes up (there are more possible pairs of digits which can be consecutive or be repeats. I created this table with a quick Python script, but is there a way we could have done it by hand?

Well, at least for the less restrictive version of the rule, yes there is (or at least of getting very close). Look at the number of 2 digit numbers which are not allowed - there are 19 of them (you can't have a 2 digit string of consecutive numbers that starts with a 9). Now for longer strings, you can essentially just consider each pair of digits as an independent experiment, which has an 81% chance of being allowable under the rule. So for 3 digit PINs, you'd expect to have 81%*81% = 65.61% of the numbers allowed - which gives exactly the right answer. For larger strings you don't quite get exactly the right answer (because the trials aren't actual independent - knowing that one set of digits is consecutive gives you some information about whether or not the others are), but it gets pretty close. 

How about for the less restrictive version? Well, it's a bit more complicated, but we I think we can still do it. The number of strings of length n which consist entirely of different digits is 10Cn * n! = 10!/(10-n)! = 10 * 9 * 8 ... * (10-n). ie, for n=2, there are 10*9 = 90 combinations, and we already know that 81 of these 90 are permissible. So, a quick calculation for how many PINs of length n should be 0.9^n*10!/(10-n)!. How close is that? We know it's exactly correct for n=2. For n=3, it gives us 0.81*(10*9*8) =  583.2, so it's pretty good. It gets slightly worse as n gets larger, for the same reason as before. 

Is there anything else we can say about these PINs? Well, let's have a look at what they look like (mostly because I wanted to play with TikZ). Here's a map of which PINs of length 4 are allowed under each rule (plotted on a 100x100 grid). This is also generated from the script above. 

There's probably supposed to be some less about password security and system design here, but I'm going to stick with pretty pictures and combinatorics instead.

The Riddler at Five Thirty Eight is a regular puzzle column that sets a puzzle to be solved over the weekend. The puzzles have ranged from completely trivial to outright dastardly. This week's puzzle is one of the more trivial ones, but it raises an interesting question. 

Here's the puzzle: 
Your wish has been granted, and you get to play tennis against Roger Federer in his prime in the Wimbledon final. You have only a 1 percent chance to win each point, but Roger, sporting gentleman that he is, offers to let you name any score and begin the match at that point. (So, if you’ve entertained a fantasy of storming back after being down three match points in the fifth set, now’s the time to live it.) What score can you name that gives you the best chance to win, and what is your chance of winning the title?

I think it's almost immediately obvious that you should choose the score to be something like 6-0 6-0 6-6 (6-0). ie, you're 6 points up in a tie breaker in order to win your third set. This means you have six match points, each of which is a 1/100 chance of glory. The probability that you miss all 6 is just under 6%. Specifically, they are 1-0.99^6 = 5.85%. You can add an extra 0.01% chance of you winning the match from 6-6 in the tiebreak, for a total probability of winning of almost exactly 5.86% - the chances of winning in any other way than winning 2 out of the first 8 points that you play are significantly less than 0.01%, so can safely be ignored.

Incidentally, this last point is the reason why you choose to be 6-0 6-0 6-6 rather than 6-0 6-0 5-0. In the latter case, the best you can do is 3 match points, for roughly a 3% chance of winning the title, and after Federer pulls the game back to level, the way tennis scoring works means that you will essentially never get another chance. Think of it this way: in order to win the game after the score is level in the game, you need to win at least two points in a row. But the chance of you winning any two points in a row is 0.01%, so all the extra chances you have by starting at 5-0 up are just multiples of 0.01%, rather than multiples of 1%, and even to get the stage where you win 2 points in a row is really, really difficult.

That raises the obvious follow up question. How good would you have to be to choose 6-0 6-0 5-0 rather than the tie breaker? I suspect if I were feeling adventurous I could calculate this by hand, but I'm not, and since I have to write this on a computer anyway, I might as well write some code that simulates tennis matches. You can see the graph on the right. The x axis is your probability of winning each point, and the y axis is your probability of winning the match. 

It's clear that the line of red circles does eventually cross the line of green triangles, but it's not until somewhere around the 40% mark. So the answer to the question "how good would you have to be to choose to be 2-0,5-0,40-0 rather than 2-0, 6-6, 6-0 up?" is very, very good indeed, good enough that you'd win about 40% of points vs. Roger Federer! Zooming in a bit (graph on the left), it looks like it actually happens at about 42%. ​

Incidentally, while I've got this code running, I might as well generate a plot of how often you win each match given different probabilities of winning points (I'm not going to take into account serving, and I'm allowing the last set to be own on a tiebreaker, since presumably the difference that makes is negligible). I've started the plot at 50, since it's obviously symmetric around this. Based on this, if you have a 45% chance of winning each point, you have just  a 5% chance of winning the match. This is pretty much the same as the chance you'd have of winning the most points at those skill differences: matches last about 250 points and the odds of a binomial distribution with 251 trials and p=0.45 generating more than 126 successes are about 5.5%. However, things rapidly go downhill for the underdog. If you have a 42% chance of winning each point, you win about .3% of the matches, whereas you win the most points about .6% of the time.  Tennis scoring does amplify skill differences, but tennis matches consist of *a lot* of points, so the better player is almost guaranteed to win, however you structure the scoring.

Finally - Ollie's version doesn't allow this solution, but the last time I heard this problem, Federer was going to play the match out up until the point you were magically transported in to finish it off. With that version, I heard the particularly neat solution that you should pick the score to be (6-0) (7-6) (6-6), where you are leading (6-0) in the tie breaker in the third set, as before, but the final score in the second set tiebreaker was something like 1,000,002-1,000,000, so that Federer is exhausted from playing the two million point tie breaker in the last match. 

You can see the (not particularly elegant) Python code that I used to generate these figure here.