## Wednesday, July 8, 2009

### Pop quiz, combinatorics

Continuing on a theme, here is an (easy) combinatorics questions:

n boys and n girls must be seated in 2n chairs. If every boy must only be seated next to a girl, how many possible seating arrangements are there?

Highlight text below for the answer.

First count the ways the boys and girls can be seated if the boys are in the odd numbered chairs and the girls are in the even number chairs. There are n odd numbered chairs, and n boys can be seated in them in $$n!$$ ways. Similarly, $$n$$ girls can be seated in the $$n$$ even numbered chairs in $$n!$$ ways. They can both be seated in $$n!^2$$ ways. Then count the ways where the boys are in even chairs and girls in odd chairs; again, there are $$n!^2$$ ways. So in total, there are $$2(n!^2)$$ ways.

### Probability!

It's time to get mathy! If you're just a programmer, these questions might seem a bit tricky for you (even if you are a math major, I hope I can get you with at least one of them). Most of them involve usage of Bayes Formula, although I will not use it, preferring a more combinatorial approach (since I'm a programmer).

Select the answer text with your mouse to view.

# Hints

Here are a few hints for you to review:
• If event A can occur in a ways, and event B can occur in b ways, and both events are mutually exclusive, A or B can occur in a+b ways.
• If event A can occur in a ways, and event B can occur in b ways, and both events are independent, A and B can occur in a*b ways.

# Question 1

A couple has two children; the first one of them is a boy. What is the probability that the other is a boy?

The probability is 1/2.

There are four ways for a couple to have two children. With G representing a girl and B representing a boy, they are: BB, BG, GB, GG. They could have a boy first, and then a girl, or a girl first, and then a boy. Of course, there are only two scenarios where a boy is the first child: BB and BG. However, in only one of those scenarios is the other child also a boy. Hence the answer is 1/2.

# Question 2

A couple has two children; one of them is a boy. What is the probability that the other is a boy?

The probability is 1/3.

Proceeding as above, there are three ways for a couple two have two children, one of them being a boy: BB, BG, and GB. However, in only one of those scenarios is the other child also a boy. Hence the answer is 1/3.

# Question 3

(Monty Hall) On a game show, you may open one of three doors and keep what is behind it. Behind one door is one million dollars, and behind the other doors are goats. You select a door to open, and the game show host randomly opens one of the other doors, revealing a goat. What is the probability that the million dollars is behind the door you didn't select?

The probability is 1/2.

Did you think this was the standard Monty Hall question? Nope! I caught you if you weren't paying attention. Read on for a solution to this question:

It's easy to enumerate all of the possible scenarios. Suppose we have the following configuration in the game show:

• Door A has one million dollars behind it
• Door B has a goat behind it
• Door C has a goat behind it

There are only six possible ways the game show could turn out:

1. You pick door A (money), and the host randomly opens door B (goat)
2. You pick door A (money), and the host randomly opens door C (goat)
3. You pick door B (goat), and the host randomly opens door A (money)
4. You pick door B (goat), and the host randomly opens door C (goat)
5. You pick door C (goat), and the host randomly opens door A (money)
6. You pick door C (goat), and the host randomly opens door B (goat)

You are given that the game show host has randomly opened a door with a goat. This means there are four events: 1, 2, 4, or 6 that could have occurred. The question asks for the probability of the door you did not choose containing the money. In events 1 and 2, there is no possible way for the money to be in the door you did not choose. But there are 2 events (events 4 and 6) where the money is in the door you did not choose. So the probability is 2/4 = 1/2.

# Question 4

Q (Monty Hall): On a game show, you may open one of three doors and keep what is behind it. Behind one door is one million dollars, and behind the other doors are goats. You select a door to open, and the game show host opens one of the other doors known not to contain the prize, revealing a goat. What is the probability that the million dollars is behind the door you didn't select?

The probability is 2/3.

The probability that the door you chose has the money behind it is 1/3. The probability that the money was behind the door that the host opened is 0. Since the probability that the money is behind one of the three doors is 1, it follows that the probability of the money being behind the door you did not choose must be 1-1/3 = 2/3.

If this is your first time hearing this, you may not be convinced. Just imagine if I divided a deck of 52 playing cards up, giving you 1 card, and keeping the rest for myself. I now ask what the probability of my holding the ace of spades is, and you reply (correctly) that it is 51/52. I then proceed to reveal 50 cards to you that I have, none of which are the ace of spades, so that we are now both holding one card each. At this point, you should surely not assume that there is only a 50% chance of my holding the ace of spades!

# Question 5

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. What is the probability that no passengers depart on the same floor?

Trick question! This problem has no solution.

I'm sorry if you spent some time trying to come up with a numerical answer to this question, as there are none. The key issue is that it is never mentioned whether or not each passenger is equally likely to depart on any given floor, or if any given floor is equally likely to have any number of departing passengers. See the next two questions to see what the difference is.

# Question 6

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. If each passenger is equally likely to depart on any floor, what is the probability that no passengers depart on the same floor?

The probability is 560 / 59049:

$$9 \cdot 8 \cdot 7 \cdot 6 \cdot 5\cdot 4\cdot 2 / {9^7} = {560} / {59049}$$

If nobody is to leave on the same floor, then the 1st passenger has any of 9 floors to depart on, the 2nd passenger has any of 8 floors to depart on (he can't pick the floor of the first passenger), the 3rd passenger has any of 7 floors (he can't pick either of the floors chosen by passengers 1 or 2), and so on. Therefore, there are (9*8*7*6*5*4*2) ways the 7 passengers can depart. However, if there are no restrictions on how passengers depart, there must be (9*9*9*9*9*9*9) = 9^7 different ways for the passengers to depart.

# Question 7

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. If each floor is equally likely to have any number of departing passengers, what is the probability that no passengers depart on the same floor?

The probability is 1 / 429.

In question 6, these two events are distinct:
A = "Passenger one departs on floor one, then passenger two departs on floor one"
B = "Passenger two departs on floor one, then passenger one departs on floor one"
However, in this scenario, we do not care about the order of departure; we only care about the number of passengers on any floor at the end of the process. We can model this problem in the following way:

Represent people with the number 0 and let 1 be a floor divider. Assuming there are only 3 people and 4 floors, this would be a possible way that nobody gets off on the same floor: 010101. As you can see, each passenger is on a different floor, and the last floor is unoccupied. Here's the other way 3 people can exit on 4 floors: 101010. The total number of ways passengers can depart is a multi-permutation: (3+3)!/(3!3!) = 5. Since there are only 2 ways that nobody can depart on the same floor, the probability for this smaller example is 2/5.

Extending to 7 people and 9 floors, we have a total of (7+8)!/(7!8!) = 1307674368000 ways for people to depart, and we can enumerate easily the number of ways that nobody departs on the same floors with our 1's and 0's:
101010101010101
011010101010101
010110101010101
010101101010101
...
010101010101011
110101010101010
101101010101010
101011010101010
...
101010101010110
Giving a total of 15 ways. Hence the probability is 15 / 6435 = 1 / 429.