Maths Olympiad Problems.........Maths Geniuses Help PLZ?

Question

1) Prove that
(1 / 15) < (1 / 2) (3 / 4) (5 / 6) ... (99 / 100) < (1 / 10)

2) Consider a 25 x 25 square grid in each of whose 625 squares is placed either 'a+1' or 'a-1'. Suppose a(i) denotes the product of all the numbers in the (i)th row and b(j) denotes the product of all the numbers in the (j)th column. Prove that a(1) + b(1) + a(2) + b(2) + ... + a(25) + b(25) is not equal to 0.

3) If p and p^2 + 2 are primes, prove that p^3 + 2 is also prime.

Thanks a lot!!!

Answer 1

1) 1/2 * 3/4 * ... * 99/100
= [99*97*95* .. *1] / [100*98*96* ... *2]
= 100! / [100*98*96* ... *2]^2
= 100! / [2*50*2*49 ... *2*1]^2
= 100! / [ 2^50 * 50!]^2
= 100! / [ 2^100 * (50!)^2 ]
= C(100, 50) * (1/2)^100

This can be considered the probability of getting exactly 50 heads in 100 tosses of a fair coin.
X ~ B(100, 0.5) ~ N(50, 5^2)
That is the binomial to normal approximation
So P(49.5 < X < 50.5)
= P(-0.1 < Z < 0.1)
= 2 * 0.0398
= 0.0796

3) The other answerers are correct with the 3rd problem.
It only works for p = 3.
For p > 3, we know that p cannot be a multiple of 3.
So p can be written 3k + 1 or 3k + 2
p^2 = 9k^2 + 6k + 1
OR 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1
So either way p^2 is in the form 3*j + 1
p^2 + 2 = 3*j + 3 = 3*(j+1), thus making it non prime.

So the only prime number, p, for which p^2 +2 is also prime, is p = 3. And for this case, p^3 + 2 is also prime.

Answer 2

>> 1) (1 / 15) < (1 / 2) (3 / 4) (5 / 6) ... (99 / 100) < (1 / 10)

If you multiply it out (a one-liner in Perl), you get

1/15 = 0.0666... < 0.079589... < 0.1 = 1/10

Symbolically, the denominator is 2^50 * 50! and the numerator is 100! / (denominator), so overall the product is

P = 100! / (2^100 * 50! * 50!) = "100 Choose 50" / 2^100

So P is the probability of tossing a fair coin 100 times and getting exactly 50 heads. You can approximate it with either Sitrling's approximation for the factorial or with the normal distribution approximation to the Binomial(N = 100, p = q = 1/2) distribution. The latter would be Prob(49.5 <= X <= 50.5) when X is normally distributed with mean Np = 50 and variance Npq = 25 (and so standard deviation 5). Thus we want the probability that a normal is within +/- 0.5/5 = +/- 0.1 standard devi
ations from the mean, which is about 0.079656, between 1/15 and 1/10. The former, Stirling's approximation, says

1 = lim n -> pos. inf. n! / (sqrt(2 pi n) (n/e)^n)

So P is approx. sqrt(2 pi 100) (100/e)^100 / (2^100 * (sqrt(2 pi 50) (50/e)^50)^2)

= 10 sqrt(2 pi) (100/e)^100 / (sqrt(2 pi) sqrt(2 pi) sqrt(50) sqrt(50) 2^100 (50/e)^100)

= (10 / 50) (1 / sqrt(2 pi) (100/e)^100 / ((100/e)^100)

= 1 / (5 sqrt(2 pi))

2 pi is 6.28... is a little over 6.25 = 2.5^2, so sqrt(2 pi) is a little over 2.5, and 5 sqrt(2 pi) is a little over 12.5. So 10 < 5 sqrt(2 pi) < 15, therefore 1/15 < (1 / (5 sqrt(2 pi))) approx= P < 1/10.



>> 2) Consider a 25 x 25 square grid in each of whose 625 squares is placed either 'a+1' or 'a-1'. Suppose a(i) denotes the product of all the numbers in the (i)th row and b(j) denotes the product of all the numbers in the (j)th column. Prove that a(1) + b(1) + a(2) + b(2) + ... + a(25) + b(25) is not equal to 0.

I think you stated this wrong. If you use 'a+1' and 'a-1' as if a were a variable, then the specified sum is a polynomial of degree at most 25 in a, and so there will be values of a which make the sum 0 (25 complex root, not necessarily distinct; at least one real root because the coefficients are real and the degree is odd).

For example, let a = 1, and assign enough a-1 labels so that each row and each column contains at least one a-1 = 0.

Instead, I think they meant to say you assign one of the values { -1, 1 } to each of the 625 squares. That is, "assign a '+1' or a '-1'."

Anyway, with that interpretation, every row product and every column product is 1 or -1.

Start with all 1's. Each row product a(i) and each column product b(j) is 1. Flip 1's to -1's one at a time and watch what happens to the sum of the a(i) + b(j). At each flip, one of the a(i) changes from -1 to 1 or vice versa, and the sum a(1) + ... + a(25) either goes up 2 or down 2. Likewise exactly one of the b(j) changes from 1 to -1 or vice versa, causing the sum b(1) + ... + b(25) to either go up 2 or go down 2. So the overall sum changes by either of

+ 2 + 2 = 4
+ 2 - 2 = 0
- 2 + 2 = 0
- 2 - 2 = -4

As each 1 is flipped to a minus 1, the sum mod 4 is left unchanged. Since the sum with all 1's was 50 = 2 mod 4, the sum for every configuration of 1's and -1's is 2 mod 4. It is never 0.


>> 3) If p and p^2 + 2 are primes, prove that p^3 + 2 is also prime.

P cannot be 2 because then p^2 + 2 = 4 + 2 = 6 is not prime.

p can be 3 because then p^2 + 2 = 9 + 2 = 11 and p^3 + 2 = 27 + 2 = 29 are all primes.

Suppose p is a prime greater than 3. p is not divisible by 3, so either p = 1 mod 3 or p = 2 mod 3. In either case, p^2 + 2 = 1 + 2 = 3 = 0 mod 3 and so 3 divides p^2 + 2 and so p^2 + 2 is not prime.

So the only time both p and p^2 + 2 are both prime is when p = 3, in which case p^3 + 2 is also a prime.



Dan

Answer 3

Mathematics
Member since: February 27, 2006
Total points: 12,070 (Level 6)
Points earned this week:
--% Best answer

Dr D
0
1) 1/2 * 3/4 * ... * 99/100
= [99*97*95* .. *1] / [100*98*96* ... *2]
= 100! / [100*98*96* ... *2]^2
= 100! / [2*50*2*49 ... *2*1]^2
= 100! / [ 2^50 * 50!]^2
= 100! / [ 2^100 * (50!)^2 ]
= C(100, 50) * (1/2)^100

This can be considered the probability of getting exactly 50 heads in 100 tosses of a fair coin.
X ~ B(100, 0.5) ~ N(50, 5^2)
That is the binomial to normal approximation
So P(49.5 < X < 50.5)
= P(-0.1 < Z < 0.1)
= 2 * 0.0398
= 0.0796

3) The other answerers are correct with the 3rd problem.
It only works for p = 3.
For p > 3, we know that p cannot be a multiple of 3.
So p can be written 3k + 1 or 3k + 2
p^2 = 9k^2 + 6k + 1
OR 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1
So either way p^2 is in the form 3*j + 1
p^2 + 2 = 3*j + 3 = 3*(j+1), thus making it non prime.

So the only prime number, p, for which p^2 +2 is also prime, is p = 3. And for this case, p^3 + 2 is also prime.

Answer 4

I answered parts 1 and 3 lasr week!
Why are you posting these questions
so many times??

Answer 5

Working on it. Keep sending those questions they are very interesting, much more interesting than some of the other questions we see posted.

Answer 6

hahahahahahahahaha for 3) sub in prime no.s? i dunno..