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?