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.

8 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.

  3. Michael Earnest says:

    What a lovely problem! If you blindly searched for the candy you want in the n – 1 boxes wihtout its label, it would take n/2 openings on average. I have found the optimal strategy is only slightly better than this. For example, when n = 100, the optimal expected number of guesses is 50 minus 0.12976297, a comparatively meager time saving.

    At any point in the process, there will be n unopened boxes. For some number, k, of these boxes, the chocolate corresponding to its label has not been found yet, while for the other n – k boxes, its chocolate has been found. The question is, which of these two categories of box should you open next? Looking at some small cases, it appears to be always better to search in one of the k – 1 boxes whose chocolate has not been found (other than the box labeled with what you are looking for). Intuitively, there is one fewer bad chocolate which can land in these boxes, making it more likely to find the good chocolate. I cannot prove this in general yet…

    Assuming this is indeed the optimal strategy, when you open a box whose chocolate has not been found, there are three cases:

    1. You find the chocolate you are looking for.
    2. The chocolate you find matches an unopened box. There are now n-1 unopened boxes, and for k-2 of them, their chocolate has not been found.
    3. The chocolate you find matches a previously opened box. There are now n-1 unopened boxes, where k-1 of their chocolates have been found.

    This idea leads to two recursive functions which solve the problem. Let D_{n,k} be the number of “partial derrangements” of {1,…,n}, where we only stipulate that numbers {1,…,k} must end up in different spots. By considering the possible entries in spot number k, this satisfies

    D_{n,k} = (k-1)D_{n-1,k-2} + (n-k)D_{n-1,k-1}

    Furthermore, of the permutations counted by D_{n,k}, the number in case 1 is D_{n-1,k-2}, the number in case 2 is (k-2) D_{n-1,k-2}, while the remaining (n-k)D_{n-1,k-1} are in case $3$.

    Next, let E_{n,k} be the expected number of boxes you must open when there are n unopened boxes, and for k of them their chocolates have not been found, assuming k >= 1. Then the preceding reasong implies

    E_{n,k} = 1 + \frac{(k-2)D_{n-1,k-2}}{D_{n,k}}\cdot E_{n-1,k-2} + \frac{(n-k)D_{n-1,k-1}}{D_{n-k}}\cdot E_{n-1,k-1}

    This leads to an easy program to compute the the desired value E_{n,n}.

    Again, this is only correct with the assumption I made about the optimal strategy. I have also written a program which drops this assumption. If you instead seach a box whose chocolate has been found, then the probability you find an unwanted chocolate corresponding to an unopened box is $(k-1)D_{n-1,k-1}/D_{n,k}$, while the probability you find a chocolate for an opened box is $(n-k)D_{n-1,k}/D_{n,k}$. Assuming this strategy were optimal, you would have

    E_{n,k} = 1 + \frac{(k-1)D_{n-1,k-1}}{D_{n,k}}\cdot E_{n-1,k-1} + \frac{(n-k)D_{n-1,k}}{D_{n-k}}\cdot E_{n-1,k}

    so you just set E_{n,k} to be the minimum of these two expressions.

    • Very interesting! (I edited your initial comment to incorporate your formula corrections.)

      “For example, when n = 100, the optimal expected number of guesses is 50 minus 0.12976297, a comparatively meager time saving.”

      Hmmm– using your description of the approach and formula, for n=100 I get a smaller value (i.e., better improvement on the naive strategy n/2) of only about 43.7294 guesses? See Mathematica implementation here, where the function v(…) implements (recursively) the minimum of your expressions, for comparison with a more explicitly brute-force-but-inefficient evaluation f(…) of optimal strategy. Results agree exactly up to n=8.

      • Michael Earnest says:

        Thank you for taking the time to reply. I think your v[n,k] function has a problem with the base cases; you should have v[n,1] = n/2 for all n >= 2, since if the only given information is that the chocolate you want is not in its box, then at best you can blindly sort through the other n – 1 boxes. Your code correctly gives v[2,1] = 1, v[3,1] = 3/2, v[4,1] = 2, but incorrectly gives v[5,1] = 2, and seems to give v[n,1] = 2 for all n >= 5.

        Indeed, the recursion for v[n,n] only goes down to the base cases v[m,1] for m <= ceil(n/2), so the earliest value affected by the incorrect base case v[5,1] would be v[9,9]. You might want to run your brute-force evaluation for n = 9 to confirm, if time allows. (I am glad you were able to write this brute-force, since I had no way of checking my answers!)

        Here is my Python solution to the problem:
        My values E[n,n] agree with your v[n,n] up to n = 8.

  4. You’re right– I updated the Mathematica gist accordingly… but had to resort to C++, with some additional optimization, to get to n=9, where our results now agree. Cool!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.