On a certain island each of the inhabitants is a member of one of the two existing clubs.

The membership distribution is such that when two random people meet, the probability of those two belonging to the same club is equal to the probability of them belonging to distinct clubs.

When 100 newcomers arrive on the island and each enrolls in one of the two clubs, the distribution still retains this feature. How many people belong to either club?

Let N be the number of inhabitants on the island, and let A be the number of members in Club Alpha.  So naturally, N-A is the number of members in Club Beta.  Now pick two persons from the island and denote their membership to be X1 and X2.  Since the P(X1=X2) = P(X1!=X2), we deduce that P(X1=X2) = 1/2

But P(X1=X2=alpha) = P(X1=alpha, X2=alpha) = P(X1=alpha)P(X2=alpha|X1=alpha) = (A/N)*[(A-1)/(N-1)] = [A(A-1)]/[N(N-1)].  Similarly, P(X1=X2=beta) = [(N-A)(N-A-1)]/[N(N-1)]

Therefore, P(X1=X2) = P(X1=X2=alpha)+P(X1=X2=beta) =
[A(A-1)+(N-A)(N-A-1)]/[N(N-1)] = 1/2

Now doing some rearrangement we find that
4A©÷-4AN+N©÷-N=0

which leads to A = (N¡¾¡îN)/2.  The reason that there is a ¡¾ sign is that if we take the + for A, then the - is for B, because A+B = (N+¡îN)/2+(N-¡îN)/2=N.

As you can see, for every N being a perfect square there is a solution for A.  To show that A is an integer, simply notice that if N is odd, then ¡îN is also odd, so their sum is even, which is divisible by 2.  Similarly, if N is even, the sum is also even.

For example, take N=4.  Then there must be 3 members in Club Alpha.

Now we add 100 to the pool.  That is equavilent as adding 100 to N, and the new A' still observe A' = (N'+¡îN')/2, where N' = N+100.  That is, we need to find all N such that N is a perfect square and N+100 is still a perfect square.

Let N=n©÷ and N+100=(n+k)©÷ where n and k are some positive integers.  Therefore (n+k)©÷-n©÷=100.  That is, (2n+k)k=100.
Since n and k are positive integers, k must divide 100.  Also, if k is odd, then 2n+k is odd and their product must be odd too, so we rule out the case as 100 is not odd.  Now since k must be even, then 2n+k must be even as well, which means 100/k is even.  So to combine all these conditions: k divides 100, k is even, 100/k is even, then all the possible choices for k are:

k=2, 10, 50, and the corresponding n are
24, 0, -24.  The last case should obviously be ruled out.

To conclude, there are only two possible scenarioes.

(I) There are 24©÷=576 inhabitants originally, (576¡¾¡î576)/2=300 or 276 of whom belongs to club Alpha.  After adding 100 people, there must be 351 or 325 of them belonging to club Alpha.

(II) There are 0 inhabitants originally and after adding 100 people, there are (100¡¾¡î100)/2 = 45 or 55 of them belonging to club Alpha.

Note: Paragraph 2 and 3 make use of two probability concepts.  First is P(A&B) = P(A)P(A|B), the conditional probability.  The second is the law of total probability, that if B[i] are disjoint and union of B[i]'s = ¥Ø, then P(A) = ¥ÒP(A&B[i]).  In the above, if X1=X2, then either X1=X2=alpha, or X1=X2=beta.

Posted by Bon on 2004-07-12 17:24:56