Puzzle

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.

*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)!