## Searching for chocolates

The following problem occurred to me, with Valentine’s Day approaching next week:

A couple of years ago, I bought a box of chocolates for Valentine’s Day.  The box contained n chocolates, indistinguishable from the outside, but the inside of each containing one of n different fillings (e.g., cherry, caramel, etc.).  On the cover of the box was a map, with labels indicating the type of each chocolate in the corresponding position.  Using the map, it was easy for me to find my favorite type of chocolate: I just find it on the map, pick it out of the box, and eat that one single chocolate.

Last year, I bought another box of chocolates.  It was the same box, containing the same n different types of chocolate… but the map was no longer printed on the box cover.  So to find my single favorite type of chocolate, I was forced to eat chocolates one at a time until I found the one I was looking for.  With no information about which chocolate was which, I expected to have to eat (n+1)/2 chocolates on average to find my favorite, by simply picking one after the other at random.

This year, I have bought another box of chocolates.  Again, it is the same box, with the same n types of chocolate, and this time the map is printed on the box cover… but as a puzzle, my wife secretly opened the box and rearranged all of the chocolates, so that all of the labels on the map are incorrect.  Now what is the optimal strategy for finding my favorite type of chocolate, and what is the corresponding (minimized) expected number of chocolates that I have to eat?

This entry was posted in Uncategorized. Bookmark the permalink.

### 4 Responses to Searching for chocolates

1. andrej says:

Should be the same as with n-1 chocolates without a map.

• Can you explain this in more detail? I’m wondering if you are maybe thinking that the re-labeling is guaranteed to be a *cyclic* permutation? To clarify, the “all incorrect” re-labeling may be an arbitrary (and uniformly chosen) derangement, not necessarily a single cycle.

2. Mendel says:

Well, you know where the chocolate you want is NOT, because it can’t be where the map says it is; so there are n-1 positions for it.
I suspect that the optimal solution will turn out to be somewhat more clever than this, but this was my first thought as well.

• Right– the problem is to determine how much more clever we can be :). One interesting point: in the box with no labels, “discovering” each new chocolate gives us no information about the likelihood of our favorite being at any particular location. But with the “all incorrect” box, that’s no longer true: for example, initially our favorite is equally likely to be in any of the n-1 other positions; but after picking one and eating it, our favorite is now no longer *equally* likely to be in any of the remaining n-2.