Permutations and Mislabeled Jars

Suppose you have three jars containing, say, jellybeans. Each jar contains a distinct flavor that any taster can unambiguously identify: sweet, sour, and a sweet-sour hybrid flavor. Each jar has a label giving the flavor, and no two jars have the same label. The problem (pun intended) is that none of the jobs are correctly labeled, and you want to correct this. Of course, you can sample each jar and relabel based on your three tastings. But suppose you’re calorie-conscious–jellybeans are, after all, sugar–and you want to minimize the number of tastes you have to make in order to correctly label the jars. What’s the minimum number of jellybeans you need to eat to complete the task?

Before I give the solution, I want to translate the preceding problem description into mathematics. We number the jars 1, 2, and 3 in order of sweet, sour, and sweet-sour. So if the jars are correctly labeled, jar 1 will contain sweet jellybeans, jar 2 will contain sour jellybeans, and jar 3 will contain sweet-sour jellybeans. Any relabeling of the jars is a permutation \sigma: \left\{1,2,3\right\}\rightarrow\left\{1,2,3\right\}. Let us denote the mislabeling of the jars by the permutation

\displaystyle\sigma:\begin{pmatrix} 1&2&3\\ \sigma(1)&\sigma(2)&\sigma(3)\end{pmatrix}

Since each jar is incorrectly labeled, the function \sigma has no fixed points; i.e., \sigma(i)\neq i for i=1,2,3. It is this hypothesis on which the solution hinges.

I claim that we only need to taste one jellybean in order to label the jars correctly. Without loss of generality–you will see that the argument is symmetric in the choice of jar–sample a jellybean from the jar labeled sweet. This tasting is equivalent to learning the value \sigma^{-1}(1). Since \sigma has no fixed points, we see that

\displaystyle \sigma^{-1}(1)=i_{1}\in\left\{2,3\right\},\indent i_{2}=\sigma^{-1}(2)\in\left\{1,3\right\},\indent i_{3}=\sigma^{-1}(3)\in\left\{1,2\right\}

If i_{1}=2, then i_{3}=1 and i_{2}=3. If i_{1}=3, then i_{2}=1 and i_{3}=2.

Advertisements
This entry was posted in math.GR, Problem Solving and tagged , , , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s