Sharing a Zodiac Sign

Date: 04/24/2001 at 23:57:15
From: Katrin
Subject: Probability

In a class of 35 students what is the probability that every student 
in the class has the same zodiac sign as at least one other classmate?

Date: 04/26/2001 at 17:01:23
From: Doctor Mitteldorf
Subject: Re: Probability

Dear Katrin,

This is an advanced question, involving the "inclusion-exclusion 
principle" for its solution. Fasten your seatbelt...

To begin with, we'll assume that all 12 signs are equally likely, even 
though we know in fact that more babies are born in the spring than in 
the fall.

We'll calculate the probability of at least one sign having exactly 
one student "stranded" in it. (Not 0, not 2, but exactly 1.) Then 
we'll subtract that number from unity to get the answer they're asking 
for.

One more preliminary: the number of ways to distribute 35 students in 
12 signs is 12^35. This is our denominator, the universe of all 
possibilities.

Now, the first step: How many ways are there to have NO students at 
all in Capricorn?

Answer:  There are 11 possible placements for 35 students, so the 
count is 11^35. The probability of this happening is 
11^35/[denominator], which is (11/12)^35 = 0.0476.

We didn't really need that number, but we're building toward the next 
calculation, which we do need: How many ways are there to distribute 
the students with EXACTLY ONE person in Capricorn? The number of ways 
of distributing the other 34 students among 11 months is 11^34. 
Multiply this by 35, because there are 35 different students who could 
be stranded in Capricorn. So our numerator is 35*11^34, and (dividing 
by the same denominator) we calculate a probability 0.1514.

That's the probability that there's exactly one student in Capricorn. 
But there are 11 other signs. Each of them has the same probability of 
stranding exactly one student. So we calculate a probability of 
12*0.1514, which is 1.816. But how did we end up with a number bigger 
than 1 for a probability?

The catch is that we've double-counted some possibilities. There are 
some cases in which there's one student stranded in Capricorn AND one 
student stranded in Aries. We counted those cases twice, once for 
Capricorn and once for Aries. We should only have counted them once. 
So we need to correct our answer by subtracting the number of cases in 
which there are two months, each stranding a student.

There are 35 students who could be stranded in Capricorn and 34 left 
for Aries, for a factor of 35*34 possibilities; the other 33 students 
could be distributed among the other 10 signs in 10^33 ways. So the 
set of possibilities we've overcounted has 35*34*10^33 members for 
each pair of months, and there are 12*11/2 = 66 pairs of months. We've 
overcounted by 66*35*34*10^33, which, when divided by our denominator, 
yields 1.3297. We're down to 0.4869 for our probability, which is a 
reasonable number since it's less than one.

Done? Not so fast. Now we've overcounted the overcount. The reason is 
that there are some possibilities in which THREE signs have stranded 
students. We need to count these possibilites and add them back. 35 
possible students for Capricorn * 34 for Aries * 33 for Sagittarius; 
the other students could be distributed in 9^32 different ways; there 
are 12*11*10/6 = 220 different triples of months. So we've overcounted 
the overcount by 220*35*34*33*9^32 which, when divided by our 
denominator, yields 0.5022. Adding to 0.4869, we have .9891.

By now you know that we're going to have to correct the correction of 
the correction as well, subtracting and adding and subtracting and 
adding all the way down to eleven-plets. I've done this on a computer, 
and for a final answer I get 0.896.

You can read more about inclusion-exclusion calculations in these 
answers from our archives:

   Probability of Matching Envelopes and Letters
   http://mathforum.org/dr.math/problems/dey3.3.98.html   

   Letters and Envelopes and the Inclusion-Exclusion Principle
   http://mathforum.org/dr.math/problems/jarrad03.27.99.html   

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/