Fruit Juice Tasting

In this puzzle, we challenge you to find the probability of guessing what flavor of juice is in each of several cans without looking at the labels.

You have been invited to a fruit-juice-tasting party. There are several cans of juice, each of a different flavor. The cans are covered with paper so that their labels are hidden.

Taste testing

You have a list of all the different flavors. You have to guess what flavor is in each can without looking at its label. In other words, you have to match each flavor on the list with a can. You can't guess a flavor more than once.

Our math puzzle this month is in two parts.

Part 1

To start you have two cans of juice. What is the probability that you will guess correctly? (Since this is a math puzzle, let's assume that you really can't taste the difference so you are just making random guesses.)

With 3 cans, what's the probability of guessing all of them correctly? What if there are 4 cans of juice? How about 10? How about 100?

Can you come up with a general formula for the probability of guessing all the flavors correctly with N cans of juice?

Part 2

Now let's look at the probability of getting all the guesses wrong. If there are only two cans of juice, then you guess either both correctly or both incorrectly. But with three cans, you could get one right and the other two wrong. What is the probability of getting all three wrong?

With 10 cans of juice, what is the probability that you will get none of them right? How about with 100 cans?

Can you come up with a general formula for the probability of getting no matches at all when trying to guess the flavors of N cans of juice?

Finally, what is the probability of getting just one right?

Course:

Math [1]
Probability [2]

Result/Solution(s)

Solution: Fruit Juice tasting math puzzle

Part 1

One way to think about this problem is to look at the number of possible ways there are to arrange the cans of juice in a row. If you have two cans, let's say orange juice and apple juice, there are two possible arrangements:

apple orange
orange apple

One of these will be the correct arrangement. Since there are two possible guesses, the probability of guessing correctly is 1 out of 2 or 1 / 2.

Let's add grape juice. There are now six possible arrangements:

apple orange grape
apple grape orange
orange apple grape
orange grape apple
grape apple orange
grape orange apple

Again, only one of these is the correct order, so your chance of guessing correctly is 1 out of 6 or 1 / 6.

If you add a fourth can, you will find that the number of possible arrangements is 24 and, therefore the probability of a correct guess is 1 / 24.

In general, the number of possible arrangements of n objects is

n x (n - 1) x . . . x 1

This is called the factorial of a number and is written n!

2! = 2
3! = 6
4! = 24

As n increases, n! increases very quickly. If you had 10 cans of juice, there would be 10! possible arrangements. 10! = 3,628,800, so your chances of guessing correctly are rather small. With 100 cans of juice there are approximately

93,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000

possible arrangements.

In general, the probability of correctly guessing all the flavors when you have n cans of juice is 1 / n!

Part 2

If you have only two cans of juice, the probability of getting them both wrong is the same as the probability of getting them both right. This is because there are only two possible arrangements:

apple orange
orange apple

One is all right. The other is all wrong.

With three flavors there are six possible arrangements:

apple orange grape
apple grape orange
orange apple grape
orange grape apple
grape apple orange
grape orange apple

Let's say that the first arrangement is correct. Then there are two arrangements that are all wrong:

orange grape apple
grape orange apple

The other arrangements have one can in the correct place and the other two in the wrong place. So the probability of guessing all wrong is 2 / 6 or 1 / 3.

In general, the question is: Given any sequence of n distinct objects, in how many ways can those objects be rearranged so that none of the objects is in its original position? This is known as the number of "derangements" of n, denoted by D(n). Another term for the number of derangements is the subfactorial denoted !n.

D(1) = !1 = 0 and D(2) = !2 = 1

One way (not the most efficient) of determining the value of D(n) for any given n is by means of the inclusion/exclusion principle. For example, with n = 5 we begin with 5! possible rearrangements, but of those rearrangements we know that 4! leave the first object unmoved, and 4! leave the second object unmoved, and so on. Thus there are 5 x 4! that leave one specific object unmoved, so we have to subtract this number. However, in doing so we have subtracted some of the arrangements twice, because some of them leave both the first AND the second element unchanged (for example). So we need to add back the number of arrangements that leave any two of the objects unmoved, of which there are C(5,2) x 3!.(*There's an explanation of what C means at the bottom of this page.) But then we need to subtract the number of arrangements that leave THREE objects unmoved, and so on. The final result is

D(5) = 1 x 5! - 5 x 4! + 10 x 3! - 10 x 2! + 5 x 1! - 1 x 0!
= 44

In general we have

n j / n
D(n) = SUM (-1) ( ) (n - j)!
j = 0 j /

If we examine the effect of multiplying each term of this sum by n + 1, we see that the value of D(n) can be computed from the value of D(n - 1) by the recurrence formula:

D(n) = n D(n - 1) + (-1)^n

The first several values of D(n) for n = 1, 2, 3 . . . are

0; 1; 2; 9; 44; 265; 1,854; 14,833 . . .

The Encyclopedia of Integer Sequences by Sloane and Plouffe, Academic Press, 1995 lists the values up to D(17), and also notes the exponential generating function

1 inf x^n
--------- = SUM D(n) ---
(1 - x) e^x n = 0 n!

Some further formulas are at http://www.madras.fife.sch.uk/maths/derangements.html [3].

*C(5,2) means the number of possible combinations of two elements at a time selected from five elements.

5!
C(5,2) = ------
2! x 3!

n!
C(n,k) = ------
k! x (n - k)!

Probability puzzle [4]
Math Puzzle [5]

apple	orange	grape
apple	grape	orange
orange	apple	grape
orange	grape	apple
grape	apple	orange
grape	orange	apple

D(5)	= 1 x 5! - 5 x 4! + 10 x 3! - 10 x 2! + 5 x 1! - 1 x 0!
	= 44