Two out of a dozen cartons have Easter eggs. Two people try to find one Easter egg carton, each using a different strategy. Who is expected to win?

Question

I have found a counter intuitive puzzle. I have read the answer given at the source and understand it completely. But, what I am unable to understand is why my intuition turned out to be wrong. Following is the question:

Alice has a dozen cartons, arranged in a 3x4 grid, which for convenience we have labeled A through L:

A	B	C	D
E	F	G	H
I	J	K	L

She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the (row-wise) order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the (column-wise) order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it's a tie.

For example, suppose Alice hides the Easter eggs in cartons H and K. Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.

Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?

Following is a rephrased version of the official solution (rephrased to make it easier to understand):

Label the cartons "A" and "L" with "xx" since both players reach those cartons simultaneously.

As far as labelling all the other cartons are concerned, label a carton with a "b", if Bob will reach it before Chris would. Similarly, label a carton with a "c", if Chris will reach it before Bob would. Also record Bob's and Chris' score upon reaching that carton.

For instance, Bob will reach the carton "B" before Chris would and Bob's score would be 2, therefore, carton B will be labelled as b2.

Therefore, the labelling of the 12 cartons would be as follows:

xx b2 b3 b4
c2 c5 b7 b8
c3 c6 c9 xx

Now, note that there are five b cartons and five c cartons. So the cases in which Alice selects carton A or carton L are equally split between Bob and Chris. Similarly if Alice selects two b cartons then Bob necessarily wins, but these are balanced out by an equal number of cases in which Alice selects two c cartons and C necessarily wins.

The crucial cases occur when Alice selects one b carton and one c carton. Bob wins if the b carton has a lower score than the c carton:

b2 and (c3 or c5 or c6 or c9)
b3 and (c5 or c6 or c9)
b4 and (c5 or c6 or c9)
b7 and c9
b8 and c9

Chris wins if the c carton has a lower score than the b carton:

c2 and (b3 or b4 or b7 or b8)
c3 and (b4 or b7 or b8)
c5 and (b7 or b8)
c6 and (b7 or b8)

Since this yields 12 cases in Bob's favor and only 11 cases in Chris's favor, Bob has the advantage.

Now, my first reaction after reading the question was that both of them will have an equal chance of winning. But, it turned out that I was wrong.

While I understand the answer, I am looking for a simpler and intuitive way to understand why it wasn't necessary that both of them would have an equal chance. And why it was necessary to look at all the possible combinations, to determine the solution.

Source: January, 2017 puzzle periodical of nsa.gov

Answer 1

(context: note that this question is asking for intuitive explanation why it's not equal, so a good answer would have to explain intuitively why the intuition that they will be equal is not the right intuition, which is what my answer is)

Because the order of who opens a specific box first is important in this case. If Chris opens a box X after Bob, then Chris has no chance to win from that box, since Bob would have opened it first. Now let's see the extreme case, where Bob opens almost all the box earlier than Chris.

Imagine Bob opening in the order A, B, C, D, E, F, G, H, I, J, K, L

And Chris opening in the order L, A, B, C, D, E, F, G, H, I, J, K (basically Bob's order, but shifted to the right once)

Now Chris only wins if at least one of the eggs is in box L and there is no egg in A, which happens only 10/55 of the time.

As Deusovi mentioned in a comment, this imbalance comes from the fact that the winner is only determined by who gets the lower number, and not by how much lower they are. In this case, Bob has 1 position advantage on 11 boxes, and Chris has 11 position advantage on 1 box.

For the original problem involving 2 eggs, we also need to consider both eggs, since the individual box analysis is only valid for one egg problem. (there could be other reasons why in the 2-egg problem we need to consider each combination, but as an intuition, looking at the imbalance in 1-egg problem should be good enough).

Answer 2

The first thing standing in the way of gaining good intuition is the mildly complicated way the first marked box to be opened is determined.

Based on the order by which they are first scanned by either player

1  2  3  4
2  5  7  8
3  6  9 10

we should use the ordering

A < B=E < C=I < D < F < J < G < H < K < L
.    .     .    B   C   C   B   B   C   .

the second row indicating the corresponding winner.

As we can see at this level B and C have equal numbers of wins. We can, however, also see that B has a tendency to win the "earlier" boxes.

Now, it is perfectly intuitive that randomly picking two boxes and then selecting the earlier one results in an overall bias towards earlier boxes.

As B is biased in the same direction it is plausible to assume that the properties "B wins on this box" and "this box is picked" are correlated and that is what all else being balanced gives B the edge.

We can make this more explicit by tabulating the full space of pairs of boxes A may choose. Accounting in terms of ordered pairs these can be represented by the upper triangle in the table of all pairs. The row index then is the earlier and therefore relevant element and the column index is the later element.

    A B E C I D F J G H K L
  +-------------------------
A |   . . . . . . . . . . .
B |     . B B B B B B B B B
E |       C C C C C C C C C
C |         . B B B B B B B
I |           C C C C C C C 
D |             B B B B B B
F |               C C C C C
J |                 C C C C
G |                   B B B
H |                     B B
K |                       C
L | 

Upper triangle geometry means that the number of entries in a given row decreases linearly with that row's index. In other words we have a linear bias towards earlier boxes.

B and C win the same number of rows but B overall wins the longer ones.

To round off the picture let us try to get some insight into why B should tend to get the earlier boxes.

Again, things are complicated by the tricky ordering imposed on us. Let try and visualise:

Both panels show the order of C in red and that of B in teal. The left one uses C as reference, the right one B. We can see that because of rotational symmetry half the time B is above C and half the time vice versa.

Using the fact that the two panels are essentially transposes of each other we can visualise our ordering:

Vertical black lines indicate a box reached first by B or at the same time and horizontal black lines indicate a box reached first by C or at the same time. The order is that along the diagonal.

While we can verify that B indeed has a slight tendency to hit earlier than C it is not clear whether there is any deeper reason for that.

To check whether there might be a systematic dependency on grid size I calculated the imbalance on a patch of grid sizes:

red squares: advantage C, blue squares: advantage B

While there is clearly some structure it is not simple. In particular, the conjecture "The player using fewer but longer lines will win" is not correct.

Answer 3

Update

Thanks to Albert.Lang for pointing out the case where this logic fails: a 4x5 pattern. Actually, there are numerous cases in which it fails, but it seems like it works in the vast majority of cases.

While it doesn’t feel good that my intuitive solution of simply looking at who has the longer lines to work with fails for all cases, I can take some comfort in knowing that intuition isn’t meant to work in all cases, only in most cases, which it does. You can see where the edge cases that make this fail exist in Albert.Lang’s posted answer.

---

TL:DR

Bob does not have to check the last row in order to have checked all of the cartons that he checks before Chris, and Chris does not have to check the last column. Given that the rows are longer than columns, this means Bob saves time over Chris.

The main body of this post is essentially my stream of consciousness approaching the answer, which is why I included the TL:DR, which more or less stands on it’s own without explanation.

---

Given that we know the two approaches (right then down and down then right) are essentially the same thing, just mirrored over the diagonal, we know that the advantage must necessarily stem from the difference in row length vs column length.

So let’s look at a more extreme example, a 3x8:

A B C D E F G H
I J K L M N O P
Q R S T U V W X

We can the translate this into fastest distances, like was done in the proposed solution:

xx  b2  b3  b4  b5  b6  b7  b8
c2  c5  c8  c11 b13 b14 b15 b16
c3  c6  c9  c12 c15 c18 c21 xx

Notice that when looking at rows, b times count ip by one, and when looking at columns c times count up by one. This is mirrored, as expected.

What is also perhaps obvious, but needs pointing out, it that whenever b occurs in a row, the count occurs sequentially for longer than when c occurs in a column.

For example, in row 1 b occurs 7 times, whereas in column 1 c occurs only 2 times. This is the crucial difference.

---

If we imagine running Bob and Chris’ methods at the same time, you’d notice that whenever Chris returns to the top of a new column, he’s starting at a point that Bob has already checked. The same is true for Bob returning to start of new rows.

Now, we know due to the “crucial difference” that Bob will traverse more elements in a single line than Chris. What that means is that Bob spends less time returning to the beginning. We also know from the last paragraph that each of the returns is visiting an already visited element (at least one).

---

Since this has somewhat been maintaining the right then down perspective, it might look like the writing is on the wall for Chris here… “Just look how many more times it has to check values at the tops of the columns, look at all that wasted time” you might be thinking. There’s just one problem… The amount of wasted time for Bob per row is larger than it is for Chris.

Now you might be thinking that the this whole explanation falls apart, because the effect seems to balance out; but worry not, for the effect from whoever has the longer lines occurs sooner.

Here’s another example to demonstrate this point:

xx  b2  b3  b4  b5  b6  b7  b8
c2  c4  c6  c8  c10 c12 c14 xx

What you see happen here is that Bob runs through the first row, taking 8 seconds, then wastes time checking each of the elements in the second row, which Chris already checked.

Chris, meanwhile, checks the first column, then checks the second column, checking an element that Bob had already checked in the process (b2), and so on through all the columns.

If Bob had to continue checking more elements in the second row, each element that he arrived at before Chris would have taken 8 seconds more than it could’ve, due to wasting time checking elements already checked by Chris.

Fortunately for Bob, he doesn’t suffer any penalty for checking the same elements as Chris, because he’s already finished, and all of the elements that he got to first were checked before checking any of the elements Chris got to first.

Chris, on the other hand, suffers the effects of Bob’s checking on every single column, because Bob had already checked the first element in each column (except first) before Chris got there, meaning the time at which Chris checked the second element in each column was 1 second later per column.

---

The two row example was a simplified one, but the principle stands for more rows.

If the last row in which Bob reaches some elements before Chris is row R, then the elements he reaches before Chris have only taken an increased amount of time based on the number of elements that Chris had reached first in rows [1, R].

Given that, we can say that the number of elements checked first by Chris that do not effect the time it took Bob to check the elements in row R is the number of elements checked first by Chris in the last row, which is, incidentally, the number of elements in the row - 1, or the number of columns.

The same is true, but mirrored, for Chris’ last column of first checked results.

So, the total number of elements that Bob reads in order to set the time it took for him to check the elements that he checks first is the total number of elements minus the number of elements in the last row (12-4=8).

For Chris, however, it is the number of elements minus the number of elements in the last column (12-3=9).

Therefore Chris has to check more elements than Bob before he’s effectively done.

Answer 4

Others have already given good answers to the question as stated, but I thought I would mention that I was the originator of this puzzle, and that the result surprised me when I first discovered it. I submitted a more general version of the puzzle to the American Mathematical Monthly; my original submission can be viewed on my website, as can the published version. One thing I found was a necessary and sufficient condition for a search order $\pi$ to not exhibit this kind of counterintuitive bias in favor of one player; namely, for each $i$, either $\pi(i)>i$ and $\pi^{-1}(i) > i$, or $\pi(i)\le i$ and $\pi^{-1}(i) \le i$. I called such search orders fair. So one answer to the question is that the search order in the puzzle is not fair. (This may not be an intuitive answer, though!)

Answer 5

Intuition is correct here in the sense that every strategy (order of opening boxes) is equally good if your goal is to find the egg in as few steps as possible. It's also correct in the sense that if you are going to play this game, and you don't know what strategy your opponent will pick, it doesn't matter which strategy you pick. The mistake is the conclusion that Bob winning most of the time against Chris means his strategy is better. This is like concluding that the fact rock beats scissors makes rock a better strategy than scissors in rock-paper-scissors.

There are 2 reasons Bob's strategy isn't better:

• as was already mentioned in other answers, it only wins because we ignore by how much you win, so you can "optimize" by designing a strategy that wins by a small amount most of the time and loses big the rest of the time, but this is kind of a red herring as it isn't really the reason, because even with ignoring by how much you win, Bob's strategy still isn't actually better than Chris'
• the real answer is that the fact that Bob's strategy wins against Chris' strategy doesn't mean it wins more in general, against any random strategy. Rock-paper-scissors.

This becomes really obvious with the following game

There are 3 cards, A, B, and C, face down on the table. One is an ace. Whoever reveals the ace in fewer steps wins.

If Bob uses the order A, B, C and Chris uses the order B, C, A, Chris wins 2/3 of the time (he wins if B or C are the ace and loses if A is the ace). When he loses, he will lose by 2 (if A is the ace, he finds it in 3 steps, while Bob finds it in 1 step), but we only count who wins, not by how much they win. However this doesn't really matter because even with the fact that we ignore by how much you win, Chris' strategy still isn't actually better - Fred's strategy of C, A, B beats Chris 2/3 of the time, but loses to Bob 2/3 of the time! Bob > Fred > Chris > Bob... All of them are equal, as intuition would suggest, but this doesn't mean each pair has an equal chance of beating each other.

ABC 1:1 vs ACB, BAC, CBA, 2:1 vs CAB, 1:2 vs BCA

ACB 1:1 vs ABC, BCA, CAB, 2:1 vs BAC, 1:2 vs CBA

...and so on. You can imagine it like a "pecking graph" where each node (strategy) has the same edges overall (same number of 1:1s, 2:1s and 1:2s), just to different other strategies (ABC has 2:1 vs CAB, while ACB has 2:1 vs BAC, etc).

Adding a second egg

Now, while the game above and Justhalf's answer explain the 1-egg case, the 2-egg case is a bit more complicated. It is actually possible for one player's strategy to win more often with 1 egg, and the other player's strategy to win more often with 2 eggs! However, the "core idea" still holds - each strategy is equally good overall (if your opponent will pick a random strategy to use against you, before they pick one your expected chance to win is the same as theirs), but this doesn't mean that each pair of strategies has an equal chance to go both ways.

Let's look at the example of the following two strategies to see that the 1-egg and 2-egg cases can have different results:

A, B, C, D, E, F, G, H, I, J, K, L (Bob)

A, K, D, F, I, E, L, C, B, G, H, J (Fred)

Here I specifically picked Fred's strategy to be worse than Bob's if there is only 1 egg, but beat Bob with 2 eggs.

We can write them out like this, the numbers signifying in which step each box is opened:

A01, B02, C03, D04, E05, F06, G07, H08, I09, J10, K11, L12 (Bob)

A01, B09, C08, D03, E06, F04, G10, H11, I05, J12, K02, L07 (Fred)

One egg

The possible outcomes are:

1. A01 - tie
2. B02, C03, E05, G07, H08, J10 - Bob wins as he picks these earlier, I'll call these BobBoxes
3. D03, F04, I05, K02, L07 - Fred wins as he picks these earlier, I'll call these FredBoxes

So with 1 egg, Bob will win 1/2 of the time, while Fred will win only 5/12 of the time.

Two eggs

1. A + BobBox - Tie (both open A first) 2 * 1/12 * 6/11 = 12/132 
2. A + FredBox - Tie 2 * 1/12 * 5/11 = 10/132 
3. BobBox + BobBox - Bob wins 6/12 * 5/11 = 30/132
4. FredBox + FredBox - Fred wins 5/12 * 4/11 = 20/132

So far Bob is winning 30/132 to 20/132, but...

BobBoxes: B02, C03, E05, G07, H08, J10

FredBoxes: D03, F04, I05, K02, L07

5. BobBox + FredBox:
  - Ties are BK, EI, GL, CD (2*4*1/12*1/11 = 8/132)
  - Bob wins BD, BF, BI, BL, CF, CI, CL, EL (2*8*1/12*1/11 = 16/132) 
  - Fred wins DE, DG, DH, DJ, FE, FG, FH, FJ, IG, IH, IJ, KC, KE, KG, KH, KJ, LH, LJ (2*18*1/12*1/11 = 36/132)

In total:

Ties: 30/132
Bob wins: 46/132
Fred wins: 56/132

Fred's strategy beats Bob with 2 eggs, despite losing with 1 egg. The reason is that BobBoxes are "weak" against FredBoxes in the case of one BobBox and one FredBox being picked, since his G, H and J can never win. This means that the "pecking graph" of strategies doesn't have the exact same structure for the 1-egg and 2-egg cases, although in most cases, the strategy which is better at 1-egg is also better at 2-egg.

Answer 6

I believe this is a good intuitive answer

Bob and Chris get an egg first at the same number of position, however the winning boxes come earlier on average for Bob (first line) than for Chris (second line).
Note: Red means a first checked box, green a last checked box.

So Bob will beat Chris finding a first egg , if there are multiple eggs hidden.
It would be equal if only 1 egg was hidden (because then the good-bad position interaction does not matter).

Some reasoning: Combinations with A are a draw, red+L cancels green+L, red+red cancels green+green, B cancels E, C cancels I. So it is enough to check combinations DFJGHK.
D+x and G+x cancel F+x and J+x, leaving Bob 1 combination (HK) advantage.

Answer 7

Consider the following cases:

1. There is an egg in A
2. There is no egg in A, but exactly one in B or E
3. There is no egg in A, B or E, but exactly one in C or I
4. There is no egg in A, B, C, E or I, but exactly one in D or F
5. There is no egg in A, B, C, D, E, F or I, but exactly one in G or J
6. Something else happens: the only remaining possibilities are BE, CI, DF, GJ, HK, HL or KL.

In case 1, the game is a draw.
In case 2, Bob wins if the one egg in B/E is in B, and Chris wins if it is in E. These are equally likely.
Cases 3, 4 and 5 are similar to case 2: if the egg is in the first slot named, Bob will win, and if not Chris will win.
So only case 6 matters. Here we can check that these options give: draw, draw, Bob, Chris, Bob, Bob, Chris. So overall Bob is (slightly) more likely to win.

The intuition really is that there are some rounds where only one person can win, starting with only Bob can win on round 4, and only Chris can win on round 5. But a win on round 4 is more likely than a win on round 5 (both determine one egg, but round 4 leaves more possibilities for the other egg), so Bob takes an early lead. Of course, you have to check that Chris doesn't catch up, but this is why they can have different chances.

Answer 8

There are some good explanations already, but here's another one:

Imagine if you will that after they choose their own path, they are made aware of their opponent's path. Then if they both allowed to change their strategy slightly so that they skip any carton that has been checked earlier in their opponent's path, then indeed their chances would be equal as intuited. This works for any two paths, even random choices.

But in this case Chris's path will check more carton's that have already been checked by Bob's path than Bob's path will, thus Bob has the advantage.