# students and classrooms

• Jan 9th 2011, 08:32 AM
Moo
students and classrooms
Hello,

I have a problem, for which I have a solution of mine, but I don't know if it's correct (and since I find a probability near $\displaystyle 0.0004$, I doubt it is (Surprised))

There are 12 students and 3 classrooms. We suppose that each student chooses independently and uniformly one of the classrooms to write an exam.
I'm looking for the probability of having at least one empty classroom.

Here is what I did (I don't want to give false ideas or whatever, so I'll put it in spoiler)
Spoiler:
My reasoning was to first find the probability that 2 rooms are empty, that is the probability that all students go to the same room : $\displaystyle 3\times\frac{1}{3^{12}}=\frac{1}{3^{11}}$.

Now let's find the probability that one room and only one is empty. Let's find the probability as if it was room 1 that is empty (we'll multiply it by 3 afterwards). This means that there is at least one student in room 2 and one student in room 3, and that the 10 remaining students go in either room.
So we "pick" a student with probability 1/12 to put in room 2, and "pick" another student with probability 1/11 to put in room 3. Then for the 10 remaining students, the probability for them to go in room 2 or 3 is $\displaystyle \left(\frac 23\right)^{10}$.

So for this second probability, I obtain $\displaystyle 3\times \frac{1}{12}\times\frac{1}{11}\times \left(\frac 23\right)^{10}$, which I add to the first probability : $\displaystyle \frac{1}{3^{11}}$.

But this gives 0.0004 and it looks so small...

Thanks for any input :)

P.S. : also, I'd like to find a formal way to put the solution since I have to explain it to someone that is not majoring in mathematics.
• Jan 9th 2011, 08:50 AM
snowtea
You can also count directly. Put the 12 students in a line. Each student chooses a classroom between 1 and 3. This is the same thing as the number of 12 digit numbers using digits 1-3. A class room is empty if the 12 digit number does not contain any one of the digits.

Count the numbers containing only 1 and 2 : 2^12
Count the numbers containing only 1 and 3 : 2^12
Count the numbers containing only 2 and 3 : 2^12
We counted numbers containing only 1, 2, or 3 twice, so subtract 3

Count all possible numbers : 3^12

Probability : (3 * 2^12 - 3) / 3^12
• Jan 9th 2011, 09:08 AM
Moo
Thanks, sounds much simpler ! (though the probability is still small oO)

Would you mind pointing out where I went wrong in my babbling, if you can and if it doesn't bother you ? :)
• Jan 9th 2011, 09:10 AM
Plato
I agree with snowtea's solution.
I did it this way. There are $\displaystyle 3^{12}$ from a set of twelve to a set of three. Then count the number of surjections from a set of twelve to a set of three: $\displaystyle \text{Surj}(12,3)=519156$.
The difference in $\displaystyle 3^{12}~\&~\text{Surj}(12,3)$ is the number of assignments leaving at least one classroom empty.
• Jan 9th 2011, 09:13 AM
snowtea
Quote:

Originally Posted by Moo
So we "pick" a student with probability 1/12 to put in room 2, and "pick" another student with probability 1/11 to put in room 3.[/tex].

This means you force a specific student in room 2 and a specific student in room 3.
E.g. "Alice" must go in room 2 and "Bob" must go in room 3.
Decreases probability quite a bit.

[Edit: Never mind what I wrote above. 1/12 is assuming the order in which the students are picked matters, and you must pick a specific student as the first]
• Jan 9th 2011, 01:55 PM
Another way to consider it is...

If we label the rooms A, B, C,
then the probability that all the students do not choose Room A is $\displaystyle \left(\frac{2}{3}\right)^{12}$

The same probabilities apply to Room B and also to Room C.

However, the probability that all the students avoid A includes the probability that they avoid "C and A" (when they are all in B) and the probability that they avoid "A and B"
(when they are all in C).

Hence, the probability that they all avoid A includes the probability that they are all in B and the probability that they are all in C.
Therefore if we subtract the probabilities of the students all being in 1 room when avoiding a specific room,
we obtain the probability that they are in 2 rooms.

Therefore the probability of at least one empty room is

$\displaystyle 3\left[\left(\frac{2}{3}\right)^{12}-2\left(\frac{1}{3}\right)^{12}\right]+3\left(\frac{1}{3}\right)^{12}$
• Jan 9th 2011, 02:45 PM
Plato
Maybe, I should explain my post #4.
This is a classical problem. This one is easy with small numbers.
Consider this one. 12 people are on a lift in a seven story building.
Each person is equally likely (and independently) to exit at any floor. What is the probability that the lift will not stop at least one floor.

Answer: $\displaystyle \desplaystyle 1-\dfrac{\text{Surj}(12,7)}{7^{12}}$
• Jan 11th 2011, 05:55 AM
Counting the number of ways of choosing 2 of the 3 rooms "by hand" seems laborious.

Labelling the rooms A, B, C.
Suppose we want to avoid room C.

First person chooses Room A with probability 1/3.
Second person chooses Room B with probability 1/3.
The remaining 10 people choose between A and B with probability $\displaystyle \left(\frac{2}{3}\right)^{10}.$

Alternatively, the first person chooses Room B with probability 1/3.
The second person chooses Room A with probability 1/3.
The remaining 10 people choose between A and B with probability $\displaystyle \left(\frac{2}{3}\right)^{10}$

Alternatively, the first and second people both choose Room A and the third person chooses B.
Or, the first and second people choose B and the third chooses A.

Then again.. the first, second and third could choose A, while the fourth chooses B...
and on and on.
That leads to an elongated probability calculation.
• Jan 11th 2011, 05:56 PM
awkward
This is the Coupon Collector's Problem. (It seems to be popular today.)