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.

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.

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.

A tough nut from Norway: RMO training !

Problem:

The integers 1, 2, 3, 4, and 5 are written on a blackboard. It is allowed to wipe out two integers a and b and replace them with a+b and ab. Is it possible, by repeating this procedure, to reach a situation, where three of the five integers on the blackboard are 2009?

Solution:

The answer is NO.

First notice that in each move, two integers will be replaced with two greater integers (except in the case where the number 1 is wiped out). Also note that from the start there are three odd integers. If one chooses to replace two odd integers on the blackboard, the number of odd integers on the blackboard decreases. If one chooses to replace two integers, which are not both odd, the number of odd integers on the blackboard is unchanged. To end up in a situation, where three of the integers on the blackboard are 2009, then it is not allowed in any move to replace two odd integers. Hence, the number 2009 can only be obtained as a sum of a+b.

In the first move that gives 2009 on the blackboard, two integers a and b are chosen such that a+b=2009 and either ab>2009 or ab=2008. In the case, ab=2008, one of the two chosen numbers is one; and hence, 1 will no longer appear on the blackboard. In either case, the two integers a+b=2009 and ab that appear in the creation of the first 2009 cannot be used anymore to create new instances of 2009. The second 2009 can only be obtained by choosing c and d such that c+d=2009 and either cd>2009 or cd=2008, and just as before; the numbers c+d=2009 and cd cannot be used in obtaining the last 2009. So, after forming two instances of 2009, there are four integers on the blackboard that have become useless for obtaining the third instance. Hence, the last integer 2009 cannot be obtained.

Wow!!

Ref: Nordic Mathematical Contest, 1987-2009.

Nalin Pithwa.

RMO Training: more help from Nordic mathematical contest

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