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?

Two other equations will help continue with generalization: x + w = y and sqrt(x) + b = sqrt(y) where w means "will come", the number of people (100 in this case) that will come onto the island, and is the only "constant" in this problem. The equation sqrt(x) + b = sqrt(y) is better rewritten as "b = sqrt(y) - sqrt(x)" because it defines b. (As used earlier, x means the number on the island before and y means the number of the island after.)

Starting with this equation: sqrt(x) + b = sqrt(y) we can show it equals a more useful form:

sqrt(x) + b = sqrt(y)

(sqrt(x) + b)^2 = (sqrt(y))^2

(sqrt(x))^2 + 2sqrt(x)b + b^2 = y and from above x + w = y

Since they both equal y, let's set them equal to each other:

x + 2sqrt(x)b + b^2 = x + w

2sqrt(x)b + b^2 = w

w = b(b + 2sqrt(x))

The final equation here is important and will be used many times through out the proof. The first rule it shows is b must be even if and only if w is and b must be odd if and only if w is odd. Since 2sqrt(x) must be even (since x is a perfect square) we can prove this as follows, putting "even" or "odd" in for b:

If w is even: odd (even + odd) = odd; even (even + even) = even. The case where b is even is the only one that works to give a w that is even.

If w is odd: odd (even + odd) = odd; even (even + even) = even. The case where b is odd is the only one that works to give a w that is odd.

The if part can be shown by similar logic: odd (even + odd) = odd; even (even + even) = even, so if b is even, w is even and if b is odd, w is odd. (The odd part doesn't need to be mentioned later since the only integer factors of and odd w are only odd anyway, but it's good to notice it.)

This first rule is important for another rule: w/b must be even if w is even. This can be proved by going back to the w = b(b + 2sqrt(x)) equation. If both sides are divided by b, the equation w/b = (b + 2sqrt(x)) will be produced. If w was even then using the equation "even + even = even" and w/b must be even.

Looking and the numbers possible for x, we see x must be at least 2 for this problem since we are told there are at least 2 people on the island. Also, given that some people came to the island, w must be greater than 0. The variable b has bounds as well. It is easy to see it must be greater than 0, but the top limit takes more work to see.

First of all, b can't be more than the square root of x since using the equation w = b(b + 2sqrt(x)) it would lead to the square root of x being negative. Using the equation again, we see b can't be the square root of w or x would be 0. Also, if b was equal to the square root of w +1, minus 1 it would work out that x was equal to 1.

w = (sqrt(w+1)-1)(sqrt(w+1)-1 + 2sqrt(x))

w = w + 1 - 2sqrt(w+1) + 1 + 2sqrt(x)(sqrt(w+1) - 2sqrt(x)

0 = - 2sqrt(w+1) + 2 + 2sqrt(x)(sqrt(w+1) - 2sqrt(x)

0 = 2(sqrt(w+1)-1)(sqrt(x)-1)

0 = (sqrt(w+1)-1)(sqrt(x)-1)

0 = sqrt(w+1)-1 or 0 = sqrt(x) -1

1 = sqrt(w+1) or 1 = sqrt(x)

1 = w+1 or 1 = x

0 = w or 1 = x

Since w can't be 0, x must be 1 here and so the case where b = sqrt(w+1) - 1 leads to a value of x that is disallowed.

Also if b = sqrt(w+1) - 1

b+1 = sqrt(w+1)

(b+1)^2 = w+1

b^2 + 2b + 1 = w + 1

b^2 + 2b = w

b(b+2) = w

This means w is divisible by b and b + 2, and since w+1 = (b+1)^2, w+1 is divisible by b+2 and this means w isn't divisible by b+1. Because b+1 = sqrt(w+1) and sqrt(w+1) is greater than sqrt(w), b is the greatest factor of w less than its square root.  This means we can conlcude these three statements can form the statement "b must be less than sqrt(w+1) -1"

Another rule to note is to minimize x, we need to maximize b since w stays constant. Finally, we need to figure out which w values are possible. Putting in the least values for b and x gives 1(2sqrt(4)+1) or 5 as the least possible w. To find another restraint for w, we can look at 2sqrt(x) because it can't be odd.  If w is even and w/2 equals an odd number then b must be even (since w is even) and this leads to 2(odd) = even(even + even) which equals 2(odd) = 4(odd) and odd = 2(odd) which is not true. This means if w is even, w/2 can't be odd. Due to the flexibility of 2sqrt(x) which may or may not be divisible by any integer greater than 2, other divisibility restrictions don't work.

So, this can be concluded as "Given an integer w greater than 5 such that it is either odd or evenly divisible by 4, the integer value of b that results in the minimization of the perfect square x is the greatest factor of w such that b is less than sqrt(w+1)-1 and w/b and b are both even if w is even." To find x given w and having figured b from that method you can use w = b(2sqrt(x) +b) when solved for x or ((w-b^2)/2b)^2 and to find a given x, you use a = (x-sqrt(x)/2)

 

Posted by Gamer on 2004-06-19 18:27:45