Earlier today I set you the following puzzle, which has been doing the rounds in the academic community, because of its counter-intuitive result. Here it is again with the solution.
The 15 boxes
Andrew and Barbara are playing a game, in which fifteen boxes are arranged in a grid as shown below.
Prizes are put in two randomly-chosen boxes. Andrew will search the boxes row by row, so his search order is ABCDEFGHIJKLMNO. Barbara will search column by column, so her order is AFKBGLCHMDINEJO.
If Andrew and Barbara open their boxes together each turn, that is, on the first turn, they both open A, on the second, Andrew opens B and Barbara opens F, on the third Andrew opens C, and Barbara opens K, and so on, who is more likely to find a prize first?
a) Andrew.
b) Barbara.
c) Both equally likely.
Solution a) Andrew.
Intuitively, it feels like both players should get to the box at the same time. If the prizes are in randomly-chosen boxes, why should one search method have an advantage over another?
Indeed, if there was only a single prize in a single box, that would be the answer: they would be equally likely to win. What changes everything is that that there are two prizes, and the game is over when the first of them is found.
Lets imagine that there is a single prize. The illustration below shows who would win the game if the prize is in that box, next to the number of the turn. Thus, if the prize is in box A, H, or O, they have an equal chance, marked ‘=’, because they both open that box on the same turn. In six boxes (on turns 2,3,4,5,9,10) Andrew wins, because he is the first to open thoses boxes, and in six boxes (on turns 2,3,5,6,9,12) Barbara wins.
Now let’s consider the situation when there are two prizes, in two randomly chosen boxes. If both prizes are in boxes that Andrew gets to first, then he wins. If both prizes are in boxes that Barbara gets to first, then she wins. Both of these occurrences are equally likely, so no one has an advantage. Likewise, we dont need to concern ourselves with prizes in boxes they both reach together, since if it is A they both win, if it is O, it reduces to the one-prize version, and if it is H, Andrew wins if the other prize is in B,C,D, or E, and Barbara does if it is in F,G,K, and L – which gives both of them equal chances.
The crucial case is when one prize is in a box Andrew gets to first, and one is in a box Barbara does. In this case, Andrew holds a slight edge, because he wins, on average, on earlier turns. (Andrew wins on 2,3,4,5,9,10, Barbara on 2,3,5,6,9,12.) For example, if the prize is in box N, which Barbara gets to on turn 12, she will always lose, because Andrew will have won by turn 10.
The puzzle was first posed (in a slightly different form) by Timothy Chow in 2010. A few years ago it was picked up by StackExchange, and more recently by Gil Kalai, a former plenary speaker at the International Congress of Mathematicians, on his blog.
The puzzle is interesting to professional mathematicians because even they struggle to find an intuitive explanation for why Andrew gets a prize first. They are surprised by the solution too.
If you can come up with a simple, intuitive explanation – please share it below!
I hope you enjoyed the puzzle. I’ll be back in two weeks.
Had I known about Chow’s puzzle, I might have included it in my latest book, Think Twice, a compilation of many counter-intuitive conundrums. (In the US it is called Puzzle Me Twice.) The idea behind the book is for it to be read on its own, or in a group, as these puzzles are great fun to be argued over.
Think Twice: Solve the simple puzzles (almost) everyone gets wrong (Square Peg, ££12.99). To support the Guardian and Observer, order your copy at guardianbookshop.com. Delivery charges may apply.
I’ve been setting a puzzle here on alternate Mondays since 2015. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.