Miscellaneous problems/solutions for RMO training: Homi Bhabha Science Foundation

Problem: 

Let f be a bijective function from the set A = \{ 1,2,3,\ldots,n\} to itself. Show that there is a positive integer M>1 such that f^{M}(1)=f(1) for each i \in A. Here, f^{M} denotes the composite function f \circ f \circ f \circ \ldots \circ f repeated M times.

Proof:

The student should be familiar with the following properties of bijective functions:

a) If f:A \rightarrow A is a bijective function then there is a unique bijective function g: A \rightarrow A such that f \circ g = g \circ f=I_{A}, the identity function on A. The function g is called the inverse of f and is denoted by f^{-1}. Thus, f \circ f^{-1}=I_{A}=f^{-1}\circ f

b) f \circ I_{A}=I_{A} \circ f

c) If f and g are bijections from A to B, then so are g\circ f and f \circ g.

d) If f, g, h are bijective functions from A to B and f \circ g = f \circ h, then g=h.

Apply f^{-1} at left to both sides to obtain g=h.

Coming to the problem, since A has n elements, we see that there are only finitely many (in fact, n!) bijective functions from A to A as each bijective function f gives a permutation of \{ 1,2,3,\ldots,n\} by taking \{ f(1), f(2), \ldots, f(n)\}. Since f is a bijective function from A to A, so is each of the functions in the sequence: f \circ f = f^{2}, f \circ f \circ f=f^{3}, \ldots, f^{n}, \ldots

All these cannot be distinct since there are only finitely many bijective functions from A to A. Hence, for some two distinct positive integers m >n, say, we must have f^{m}=f^{n}

If n=1, we take $, latex M=m$, to obtain the result. If n>1, multiply both sides by (f^{-1})^{n-1}, to get f^{m-n-1}=f. We take M=m-n+1 to get the relation f^{M}=f when M>1.

Note this means f^{M}(i)=f(i) for all i \in A.

Aliter:

Take any element r in the set A and consider the sequence of elements

r, f(r), (f \circ f)(r), (f \circ f \circ f)(r), \ldots

obtained by applying f successively. Since A has only n elements there must be repetitions in the above sequence. But, when the first repetition occurs, this must be r itself, for, if the above sequence looks (for instance) like:

r, a, b, c, d, e, c, \ldots where the first repetition is an element c other than r, this would imply f(b)=c and f(e)=c contradicting the fact that f is a bijection. Thus, for some positive integer l_{r} \geq 1, we have f^{l_{r}}=r.

This is true for each r in the set A=1,2, \ldots, n. By taking M to be the lcm of l_{1}, l_{2}, \ldots, l_{r}, we get

f^{M}(r)=r for each r \in A.

Note: If f itself is the identity function the above proof fails because each l_{r}=1. But, in this case, we may take M to be any integer greater than or equal to 2.

Problem:

Show that there exists a convex hexagon in the plane such that:

(a) all its interior angles are equal, (b) its sides are 1,2,3,4,5,6 in some order.

Proof:

Let ABCDEF be an equiangular hexagon with side-lengths as 1,2,3,4,5,6 in some order. We may assume WLOG that AB=1. Let BC=a, CD=b, DE=c, EF=d, FA=e.

Since the sum of all the angles of a hexagon is equal to (6-2) \times 180 \deg=720 \deg, it follows that each interior angle must be equal to \frac{720 \deg}{6}=120 \deg. Let us take A as the origin, the positive x-axis along AB and the perpendicular at A to AB as the y-axis. Use vectors. If the vector is denoted by (x,y), we then have

\overline {AB}=(1,0)

\overline {BC}=(a\cos{60 \deg},a \sin{60\deg})

\overline {CD}=(b\cos{120\deg},b\sin{120 \deg})

\overline{DE}=(c\cos{180\deg},c\sin{180\deg})=(-c,0)

\overline{EF}=(a\cos {240} \deg, d\sin {240}\deg),

\overline{FA}=(e\cos {300}\deg, e\sin{300}\deg)

This is because these vectors are inclined to the positive x-axis at angles 0 \deg, 60 \deg, 120 \deg, 180 \deg, 240\deg, 300 \deg respectively.

Since the sum of all these 6 vectors is \overline{0}, it follows that 1+\frac{a}{2}-\frac{b}{2}-c-\frac{d}{2}+\frac{e}{2}=0,

and, (a+b-d-e)\frac{\sqrt{3}}{2}=0. That is, a-b-2c-d+e+2=0…call this I

and a+b-d-e=0….call this II.

Since \{a,b,c,d,e \} = \{2,3,4,5,6 \}, in view of II, we have the following:

(i) \{a,b \}=\{2,5 \}, \{d,e \}=\{ 3,4\}, c=6

ii) \{ a,b\}=\{ 3,6\}, \{d,e \}=\{4,5 \}, c=2.

iii) \{a,b \}=\{2,6 \}, \{d,e \}=\{3,5 \}, c=4

Note: the possibility that \{ a,b\}=\{3,4 \} and \{ d,e\}=\{ 2,5\} in (i), for instance,need not be considered separately, because we can reflect the figure about x=\frac{1}{2} and interchange these two sets.

Case (i):

Here, (a-b)-(d-e)=2c-2=10. Since a-b= \pm 3, d-e= \pm 1, this is not possible.

Case (ii):

Here, (a-b)-(d-e)=2c-2=2$. This is satisfied by (a,b,d,e)=(6,3,5,4)

Case (iii):

Here, (a-b)-(d-e)=2c-2=6

This is satisfied by (a,b,d,e)=(6,2,3,5).

Hence, we have essentially two different solutions: (1,6,3,2,5,4) and (1,6,2,4,3,5). It may be verified that (I) and (II) are both satisfied by these sets of values.

Aliter:

Consider an equilateral triangle of side 9 units. Remove from the three corners equilateral triangles of sides 1 unit, 2 units, and 3 units respectively. The remaining portion is now an equiangular hexagon ABCDEF with sides 1,6,2,4,3,5 as required.

Problem:

There are ten objects with total weight 20, each of the weights being a positive integer. Given that none of the weights exceed 10, prove that the ten objects can be divided into two groups that balance each other when placed in the two pans of a balance.

Solution:

Let a_{1}, a_{2}, \ldots, a_{10} denote the weights of the 10 objects in decreasing order. It is given that 10 \geq a_{1} \geq a_{2} \geq \ldots a_{10} \geq 1 and that a_{1}+a_{2}+ \ldots + a_{10}=20. For each i, 1 \leq i \leq 9, let S_{i}=a_{1}+ \ldots + a_{i}. (For example, S_{1}=a_{1}, S_{2}=a_{1}+a_{2}, etc.Consider the 11 numbers 0, S_{1}, S_{2}, \ldots, S_{9}, a_{1}-a{10}. Note that all these 11 numbers are non-negative and we have 0 \leq a_{1}-a_{10}<10 and 1<S_{i}<20 for 1 \leq i \leq 9. Now, look at the remainders when these 11 numbers are divided by 10. We have 10 possible remainders and 11 numbers and hence, by the Pigeon Hole Principle at least some two of these 11 numbers have the same remainder.

Case (i):

For some j, S_{j} has the remainder 0, that is, S_{j} is multiple of 10. But, since 1<S_{j}<20, the only possibility is that S_{j}=10. Thus, we get a balancing by taking the two groups to be a_{1}, \ldots, a_{j} and a_{j+1}, \ldots, a_{10}.

Case (ii):

Suppose a_{1}-a_{10} is a multiple of 10. But, then since 0 \leq a_{1}-a_{10}<10, this forces a_{1}-a_{10}=0, which, in turn, implies that all the weights are equal and equal to 2 as they add up to 20. In this case, taking any five weights in one group and the remaining in the other we again get a balancing.

Case (iii):

For some j and k, say j<k,  we have that S_{j} and S_{k} have the same remainder, that is, S_{k}-S_{j} is a multiple of 10. But, again since 0<S_{k}-S_{j}<20, we should have S_{k}-S_{j}=10, that is, a_{k}+a_{k-1}+\ldots + a_{j+1}=10, and we get a balancing.

Case (iv):

Suppose (a_{1}-a_{10}) and S_{j} for some j (1 \leq j \leq 9) have the same remainder, that is, S_{j}-(a_{1}-a_{10}) is a multiple of 10. As in the previous cases, this implies that S_{j}-(a_{1}-a_{10})=10. That is, a_{2}+a_{3}+ \ldots + a_{j}+a_{10}=10. Hence, \{a_{2},a_{3}, ldots, a_{j},a_{10} \} and \{ a_{1}, a_{j+1}, \ldots, a_{9}\} balance each other.

Thus, in all cases, the given 10 objects can be split into two groups that balance each other.

Problem:

At each of the eight corners of a cube write +1 or -1 arbitrarily. Then, on each of the six faces of the cube write the product of the numbers written at the four corners of that face. Add all the fourteen numbers so written down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that this final sum is zero?

Solution:

Let x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8} be the numbers written at the corners. Then, the final sum is given by

\sum_{i=1}^{8}x_{i}+x_{1}x_{2}x_{3}x_{4}+x_{5}x_{6}x_{7}x_{8}+x_{1}x_{4}x_{5}x_{8}+x_{2}x_{3}x_{6}x_{7}+x_{1}x_{2}x_{5}x_{6}+x_{3}x_{4}x_{7}+x_{8}.

Because there are fourteen terms in the above sum, and each of the terms is +1 or -1, the sum will be zero only if some seven terms are +1 each and the remaining 7 terms are -1 each.

But, the product of the fourteen terms is (x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}x_{7}x_{8})^{4}=(\pm 1)^{4}=+1.

Therefore, it is impossible to have an odd number of -1’s in the above sum.

We conclude that the desired arrangement is not possible.

Problem:

Given the 7-element set A= \{ a,b,c,d,e,f,g\}, find a collection T of 3-element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.

Solution:

One possible solution collection is as follows:

\{ a, b, c\}, \{ a,d,e\}, \{a, f, g\}, \{ b,d,f\}. \{b,e,g \}, \{ c,e,f\}, \{ c,d,g\}. Note that there could be other combinations obtained by permitting the letters. WLOG, a can be associated with three pairs b,c,d; e, f, g. Now b can be associated with d, f and e, g. The possible choices left for c are only the pairs e,f and d,g. This arrangement does work.

Hope you all enjoy such type of questions. Please compare your attempts with the solutions given above.

Cheers,

Nalin Pithwa.

Reference: Problem Primer for the Olympiad, C. R. Pranesachar, B J Venkatchala, C. S. Yogananda, 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=1519266188&sr=1-2&keywords=problem+primer+for+the+olympiad

If you are interested in knowing more about the RMO and INMO, please refer to:

http://olympiads.hbcse.tifr.res.in/

RMO (Homi Bhabha Science Foundation): some miscellaneous problems to practise

Problem 1:

Let f be an bijective function (one-one and onto) from the set A=\{ 1,2,3, \ldots, n\} to n itself. Show that there is a positive integer M>1 such that f^{M}(i)=i for each i \in A.

Note: f^{M} denotes the composite function f \circ f \circ f \circ \ldots \circ f repeated M times.

Problem 2:

Show that there exists a convex hexagon in the plane such that : (a) all its interior angles are equal (b) its sides are 1,2, 3, 4, 5, 6 in some order.

Problem 3:

There are ten objects with total weight 20, each of the weights being a positive integer. Given that none of the weights exceed 10, prove that the ten objects can be divided into two groups that balance each other when placed on the two pans of a balance.

Problem 4:

At each of the eight corners of a cube, write +1 or -1 arbitrarily. Then, on each of the six faces of the cube write the product of the numbers written at the four corners of that face. Add all the fourteen numbers so written down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that the final sum is zero?

Problem 5:

Given the seven element set A= \{a,b,c,d,e,f,g \}, find a collection T of 3-element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.

Solutions will be put up tomorrow. Meanwhile, make a whole-hearted attempt to crack these!

Cheers,

Nalin Pithwa

PS: In case you want more, information, please visit:

http://olympiads.hbcse.tifr.res.in/

PS: I am not in any official way connected to the above official conductors of the exam.

Inequalities and mathematical induction: RMO sample problems-solutions

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

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

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

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 or Pre-RMO training: Homibhabha Science Foundation exam

Sample questions based on logic only:

  1. Given 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 alll the sixty four entries are in fact equal.
  2. Let T be the set of all triples (a,b,c) of integers such that 1 \leq a <b<c \leq b. For each triple (a,b,c) in T, take the product abc. Add all these products corresponding to all triples in F. Prove that the sum is divisible by 7.
  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 get 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.

Any ideas ? Please wait for solutions tomorrow.

Nalin Pithwa.