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 , and in order of sweet, sour, and sweet-sour. So if the jars are correctly labeled, jar will contain sweet jellybeans, jar will contain sour jellybeans, and jar will contain sweet-sour jellybeans. Any relabeling of the jars is a permutation . Let us denote the mislabeling of the jars by the permutation
Since each jar is incorrectly labeled, the function has no fixed points; i.e., for . 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 . Since has no fixed points, we see that
If , then and . If , then and .