madhava mathematics competion

Inequalities and mathematical induction: RMO sample problems-solutions

Posted by

0

Problem:

1. Prove the inequality —- 2^{n}(n!)^{2} \leq (2n)! for all natural numbers greater than or equal to 1.

Proof 1:

First consider the following: 2.6. 10.14 \ldots (4n-2)=\frac{(2n)!}{n!}. Let us prove this claim first and then use it to prove what is asked: Towards, that end, consider

RHS = \frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)\ldots 4.2.1}{1.2.3.4\ldots (n-1)n}=LHS, cancelling off the common factors in numerator and denominator of RHS. (note this can also be proved by mathematical induction! 🙂 )

In the given inequality:

we need to prove 2^{n}(n!)^{2} \leq (2n)!

consider 2.6.10.14. \ldots (4n-2)=\frac{(2n)!}{n!} where

LHS = (2.1)(2.3) (2.5) (2.7) \ldots 2(n-1), this is an AP with first term 2 and nth term (4n-2) and common difference 4; there are n factors “2”; hence, we 2^{n}1.3.5.7 \ldots (n-1)=\frac{(2n)!}{n!} so we get

2^{n} (n!) 1.3.5.7.\ldots (n-1) = (2n)!; multiplying and dividing RHS of this by 2.4.6.8.\ldots n, we get the desired inequality. Remember the inequality is less than or equal to.

Problem 2:

Establish the Bernoulli inequality: If (1+a) > 0, then (1+a)^{n} \geq 1+na.

Solution 2:

Apply the binomial theorem, which in turn, is proved by mathematical induction ! 🙂

Problem 3:

For all natural numbers greater than or equal to 1, prove the following by mathematical induction:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{n^{2}} \leq 2-\frac{1}{n}

Proof 3:

Let the given proposition be P(n).

Step 1: Check if P(1) is true. Towards that end:

LHS=\frac{1}{1^{2}}=1 and $latex RHS=2-\frac{1}{1}=2-1=1$ and hence, P(1) is true.

Step 2: Let P(n) be true for some n=k, k \in N. That is, the following is true:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} \leq 2 -\frac{1}{k}

Add \frac{1}{(k+1)^{2}} to both sides of above inequality, we get the following:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} + \frac{1}{(k+1)^{2}} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^{2}}

Now, the RHS in above is 2-\frac{1}{k} +\frac{1}{(k+1)^{2}}=2-\frac{k^{2}+k+1}{k(k+1)^{2}}. We want this to be less than or equal to 2-\frac{1}{k+1}. Now, k \in N, k>1, so what we have to prove is the following:

-\frac{k^{2}+k+1}{k(k+1)^{2}} \leq -\frac{1}{k+1}, that is, we want to prove that

(k+1)(k^{2}+k+1) \geq k(k^{2}+2k+1), that is, we want k^{3}+k^{2}+k+k^{2}+k+1 \geq k^{3}+2k^{2}+k, that is, we want k+1 \geq 0, which is obviously true. QED.

Cheers,

Nalin Pithwa.

Pre RMO or RMO Solutions: Homi Bhabha Science Foundation

Posted by

0

Problem:

Reference: Problem Primer for the Olympiad by C. R. Pranesachar, et al. Prism Books

Amazon India link: https://www.amazon.in/Problem-Primer-Olympiad-2Ed-Pranesachar/dp/8172862059/ref=sr_1_2?s=books&ie=UTF8&qid=1518894790&sr=1-2&keywords=problem+primer+for+the+olympiad

Five men A, B, C, D, E are wearing caps of black or white colour without each knowing the colour of his own cap. It is known that a man wearing a black cap always speaks the truth while a man wearing a white cap always lies. If they make the following statements, find the colour of the cap worn by each of them:

A: I see three black and one white cap.

B: I see four white caps.

C: I see one black and three white caps.

D: I see four black caps.

Solution:

Suppose E is wearing a white cap:

Then, D is lying and hence must be wearing a white cap. Since D and E both have white caps, A is lying and hence, he must be wearing white cap. If C is speaking truth, then C must be wearing a black cap and B must be wearing a black cap as observed by C. But, then B must observe a black cap on C. Hence, B must be lying. This implies that B is wearing a white cap which is a contradiction to C’s statement.

On the other hand, if C is lying, then C must be wearing a white cap. Thus, A, C, D and E are wearing white caps which makes B’s statement true. But, then B must be wearing a black cap and this makes C statement correct.

Thus, E must be wearing a black cap. This implies that B is lying and hence, must be having a white cap. But, then D is lying and hence, must be having a white cap since B and D have white caps. A is not saying the truth. Hence, A must be wearing a white cap. These together imply that C is truthful. Hence, C must be wearing a black cap. Thus, we have the following distribution:

A: white cap; B: white cap; C: black cap; D: white cap; E: black cap.

Hope you enjoyed it! There can be some other approaches too starting with some other assumption(s).

Nalin Pithwa.

Pre-RMO or RMO sample problem solutions: logic questions

Posted by

0

Reference: Problem Primer for the Olympiad by C. R. Pranesachar et al, Prism Books.

Amazon India link:

https://www.amazon.in/Problem-Primer-Olympiad-2Ed-Pranesachar/dp/8172862059/ref=sr_1_2?s=books&ie=UTF8&qid=1518891874&sr=1-2&keywords=problem+primer+for+the+olympiad

Problem 1:

The sixty four squares of a chess board are filled with positive integers one on each in such a way that each integer is the average of the integers on the neighbouring squares. (Two squares are neighbours if they share a common edge or vertex. Thus, a square can have 8, 5, or 3 neighbours depending on its position). Show that all the sixty four entries are in fact equal.

Solution 1:

Consider the smallest value among the 64 entries on the board. Since it is the average of the surrounding numbers, all those numbers must be equal to this number as it is the smallest. This gives some more with the smallest value. Continue in this way till all the squares are covered.

Problem 2:

Let T be the set of all triples (a,b,c) of integers such that 1 \leq a < b <c \leq 6. For each triple (a,b,c) in F, take the product abc. Add all these products corresponding to all triples in T. Prove that the sum is divisible by 7.

Solution 2:

For every triplet (a,b,c) the triplet (7-c,7-b,7-a) is in T and these two are distinct as 7 \neq 2b. Pairing off (a,b,c) with (7-c,7-b,7-a) for each (a,b,c) \in T. 7 divides abc-(7-c)(7-b)(7-a).

Problem 3:

In a class of 25 students, there are 17 cyclists, 13 swimmers, and 8 weight lifters and no one is all the three. In a certain mathematics examination, 6 students got grades D or E. If the cyclists, swimmers and weight lifters all got grade B or C, determine the number of students who got grade A. Also, find the number of cyclists who are swimmers.

Solution 3:

Let S denote the set of all 25 students in the class, X the set of swimmers in S, Y the set of all weight lifters and Z the set of all cyclists. Since students in X \bigcup Y \bigcup Z all get grades B and C and six students get grades D or E, the number of students in X \bigcup Y \bigcup Z \leq 25-6=19. Now assign one point to each of the 17 cyclists, 13 swimmers, and 8 weight lifters. Thus, a total of 38 points would be assigned among the students in X \bigcup Y \bigcup Z. Note that no student can have more than two points as no is all the three. Then, we should have |X\bigcup Y \bigcup Z| \geq 19 as otherwise 38 points cannot be accounted for. (For example, if there were only 18 students in X \bigcup Y \bigcup Z the maximum number of points that could be assigned to them is 36). Therefore, |X \bigcup Y \bigcup Z|=19 and each student in  X \bigcup Y \bigcup Z is in exactly 2 of the sets X, Y and Z. Hence, the number of students getting grade A=25 - 19-6=0, that is, no student gets A grade. Since there are 19-8=11 students who are not weight lifters all these 11 students must be both swimmers and cyclists. (Similarly, there are 2 who are both swimmers and weight lifters and 6 who are both cyclists and weight lifters).

More later,

Nalin Pithwa

Pre-RMO or RMO tutorial: Homi Bhabha Science Foundation

Posted by

0

Some more questions based on logic only:

  1. Five men A, B, C, D, E are wearing caps of black or white colour without each knowing the colour of his cap. It is known that a man wearing a black cap always speaks the truth while a man wearing a white cap always lies. If they made the following statements, find the colour of the cap worn by each of them:

A: I see three black and one white cap.

B: I see four white caps.

C: I see one black and three white caps.

D: I see four black caps.

So, put on your thinking cap and send me comments/answers !

Nalin Pithwa.

RMO Training: more help from Nordic mathematical contest

Posted by

0

Problem:

32 competitors participate in a tournament. No two of them are equal and in a one against one match the better always wins. (No tie please). Show that the gold, silver and bronze medal can be found in 39 matches.

Solution:

We begin by determining the gold medallist using classical elimination, where we organize 16 pairs and matches, then 8 matches of the winners, 4 matches of the winners in the second round, then 2-semifinal matches and finally one match making 31 matches altogether.

Now, the second best player must have at some point lost to the best player, and as there were 5 rounds in the elimination, there are 5 candidates for the silver medal. Let C_{i} be the candidate who  lost to the gold medalist in round i. Now, let C_{1} and C_{2} play, the winner play against C_{3}, and so forth. After 4 matches, we know the silver medalist; assume this was C_{k}.

Now, the third best player must have lost against the gold medalist or against C_{k} or both. (If the player had lost to someone else, there would be at least three better players.) Now, C_{k} won k-1 times in the elimination rounds, the 5-k players C_{k+1}\ldots C_{5} and if k is greater than one, one player C_{j} with j<k. So there are either (k-1)+(5-k)=4 or (k-1)+(5-k)+1=5 candidates for the third place. At most 4 matches are again needed to determine the bronze winners.

Cheers to Norway mathematicians!

Nalin Pithwa.

Reference: Nordic mathematical contests, 1987-2009.

Amazon India link:

https://www.amazon.in/Nordic-Mathematical-Contest-1987-2009-Todev/dp/1450519830/ref=sr_1_1?s=books&ie=UTF8&qid=1518386661&sr=1-1&keywords=Nordic+mathematical+contest

RMO Training: taking help from Nordic mathematical contest: 1988

Posted by

0

Problem:

Let m_{n} be a smallest value of the function f_{n}(x)=\sum_{k=0}^{2n}x^{k}. Prove that m_{n} \rightarrow \frac{1}{2} when n \rightarrow \infty.

Proof:

For n>1,

f_{n}(x)=1+x+x^{2}+\ldots=1+x(1+x+x^{2}+x^{4}+\ldots)+x^{2}(1+x^{2}+x^{4}+\ldots)=1+x(1+x)\sum_{k=0}^{n-1}x^{2k}.

From this, we see that f_{n}(x)\geq 1 for x \leq -1 and x\geq 0. Consequently, f_{n} attains its maximum value in the interval (-1,0). On this interval

f_{n}(x)=\frac{1-x^{2n+1}}{1-x}>\frac{1}{1-x}>\frac{1}{2}

So, m_{n} \geq \frac{1}{2}. But,

m_{n} \leq f_{n}(-1+\frac{1}{\sqrt{n}})=\frac{1}{2-\frac{1}{\sqrt{n}}}+\frac{(1-\frac{1}{\sqrt{n}})^{2n+1}}{2-\frac{1}{\sqrt{n}}}

As n \rightarrow \infty, the first term on the right hand side tends to the limit \frac{1}{2}. In the second term, the factor

(1-\frac{1}{\sqrt{n}})^{2n}=((1-\frac{1}{\sqrt{n}})^{\sqrt{n}})^{2\sqrt{n}}

of the numerator tends to zero because

\lim_{k \rightarrow \infty}(1-\frac{1}{k})^{k}=e^{-1}<1.

So, \lim_{n \rightarrow \infty}m_{n}=\frac{1}{2}

auf wiedersehen,

Nalin Pithwa.

Reference: Nordic Mathematical Contest, 1987-2009.

 

An easy inequality from Nordic mathematical contests !?

Posted by

0

Reference: Nordic Mathematical Contest, 1987-2009, R. Todev.

Question:

Let a, b, and c be real numbers different from 0  and a \geq b \geq c. Prove that inequality

\frac{a^{3}-c^{3}}{3} \geq abc(\frac{a-b}{c} + \frac{b-c}{a})

holds. When does the equality hold?

Proof:

We know that a, b and c are real, distinct and also non-zero and also that a \geq b \geq c.

Hence, c-b \leq 0 \leq a-b, we have (a-b)^{3}\geq (c-b)^{3}, or

a^{3}-3a^{a}b+3ab^{2}-b^{3} \geq c^{3}-3bc^{2}+3b^{2}c-b^{3}

On simplifying this, we immediately have

\frac{1}{3}{(a^{3}-c^{3})} \geq a^{2}b-ab^{2}+b^{2}c-bc^{2}=abc(\frac{a-b}{c}+\frac{b-c}{a}).

A sufficient condition for equality is a=c. If a>c, then (a-b)^{3}>(c-b)^{3}. which makes the proved inequality a strict one. So, a=c is a necessary condition for equality too.

-Nalin Pithwa.