| The article this week is a puzzle that comes from the NSA!For the last couple of years, the NSA web site has hosted a monthly puzzle. This puzzle was originally published in September 2015. They republished it again earlier this year. |  |
For the last couple of years, the NSA web site has hosted a monthly puzzle. This puzzle was originally published in September 2015. They republished it again earlier this year.
Easter Egg Hunt Puzzle
|
|Lucy decides to play a game with her two colleagues. She has twelve boxes and two Easter Eggs. She, randomly, places the two Eggs (one per box) into the cartons, then seals all the cartons up. She then arranges the boxes into a rectangular pattern of four by three. The layout is show below. (I’ve labelled the boxes so we can describe the system).|
| Bob and Charlie hunt for eggs by opening boxes. They select a box, open it, and look inside for an egg. They stop when they find their first egg, and their score is the number of boxes they had to open. The player with the lowest score wins. |  |
 |
Both Bob and Charlie both apply a methodical search strategy. Both start at the top left corner.Bob’s strategy is to move horizontally through all the boxes in a row, then advance to the next row, then onto the next row if needed; stopping when his first egg is encountered (A→B→C→D→E→F…) |
Bob’s strategy is to move horizontally through all the boxes in a row, then advance to the next row, then onto the next row if needed; stopping when his first egg is encountered (A→B→C→D→E→F…)
|
|The hunt is then reset to the original state, and Charlie gets to hunt.Charlie also starts in the top left, but searches vertically down the column of boxes, advancing along on as necessary (A→E→I→B→F…)|
Charlie also starts in the top left, but searches vertically down the column of boxes, advancing along on as necessary (A→E→I→B→F…)
For example, suppose Lucy hides the Easter eggs in cartons H and K.
Bob will stop after reaching the egg in carton H and will score 8, whilst Charlie will stop after reaching the egg in carton K and will score 9. Bob wins in this case. The subtle issues here are that there are two eggs, not one, and that the layout of the boxes is not square.
The question is, who has the better strategy?
Is Bob more likely to find an egg first? Is Charlie? Or are both strategies equally as likely to win?
Who has the better strategy?
Solving
There are many ways to solve this, both theoretically and practically. I’ll look at two theoretical ways. (A practical way would be to simulate the system; randomly placing the two eggs, and then testing out each strategy many times, keeping track of who wins. You could do this manually, or get a computer to perform it millions of times. If you had a fair random number generator, you could come up with the answer. This way of coming with an answer is called a Monte-Carlo simulation).
Brute force
There are only 12C2 (12 choose 2) ways the eggs could be hidden in the boxes. This is just 66 possible combinations. We could write code to iterate through each of these configurations and count the number of times each person wins, and also when the game ends in a tie.
I did this, and here are the results. Bob wins in 27/66 of the configurations. Charlie wins in 26/66 configurations, and it’s a tie in 13/66 of the configurations. We can see from this that Bob is slightly more likely to win.
Bob has a slight advantage!
Logic
We can understand more about why Bob has the advantage by logically analyzing the system.
|
|To the left is a matrix showing which of the players gets to that box first.It shows, if an egg were to be be placed in that box, who would have gotten there first.|
It shows, if an egg were to be be placed in that box, who would have gotten there first.
If an egg were placed in A (the first box), or L (the last box), it’s a tie. If any egg were placed in A, it would be the first egg encountered, and by definition, this is a tie.
- If any egg were placed in L, then the other egg would have to have been encountered before this, and examination of the matrix shows that five of the cartons are an advantage to Bob, and five are an advantage to Charlie (plus one automatic tie), so it’s a wash with advantage to neither player.
The above situations covers the cases where one (or both) of the eggs were placed in a box that results in tie. There are more cases to consider.
If Lucy placed both eggs in cartons that were advantageous to Bob, this would guarantee a win for Bob. Similarly, if she placed both eggs in cartons that were advantageous to Charlie, he would definetly win. As above, however, since there are an equal number of boxes that are advantageous to each player, again this is a wash. No player has an advantage in this scenario.
The final case to consider is the case that Lucy places one egg in a box that is advantageous to Bob and one that is advantageous to Charlie. In these mixed parity placings we need to consider which egg would be enecountered first to secure the victory.
|
|To do this we need to know, not just who would win an egg in that box, but also the score (number of moves) obtained if that egg was found first.The matrix on the left shows the score that would be obtained by each player if that egg was the winning egg.|
The matrix on the left shows the score that would be obtained by each player if that egg was the winning egg.
Bob wins if the carton he has advantage with has a lower number than carton that Chalie has an advantage with. Here are the situations where Bob wins:
-
Box B[2] and ( Box I[3] or Box F[5] or Box J[6] or Box K[9] )
-
Box C[3] and ( Box F[5] or Box J[6] or Box K[9] )
-
Box D[4] and ( Box F[5] or Box J[6] or Box K[9] )
-
Box G[7] and Box K[9]
-
Box H[8] and Box K[9]
Charlie wins if the carton he has advantage with has a lower number than the carton that Bob has an advantage with. Here are those cases:
-
Box E[2] and ( Box C[3] or Box D[4] or Box G[7] or Box H[8] )
-
Box I[3] and ( Box D[4] or Box G[7] or Box H[8] )
-
Box F[5] and ( Box G[7] or Box H[8] )
-
Box J[6] and ( Box G[7] or Box H[8] )
Since this yields 12 cases in Bob’s favor and only 11 cases in Charlie’s favor, Bob has the advantage.
This confirms the result we obtained by brute forcing all permutations.
Bob has a slight advantage!
You can find a complete list of all the articles here.
Click here to receive email alerts on new articles.