Home Blog About Us Work we do Content Contact Us
 

Newsletter: Click here to join an email list and be contacted when a new article is published.

 

 

 Advertisement 

Easter Egg Puzzle

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.

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…)

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…)

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 29/66 of the configurations. Charlie wins in 28/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.

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.

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:

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:

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.

© 2009-2017 DataGenetics    Privacy Policy