Miscellaneous questions: part I : solutions: tutorial practice preRMO and RMO

The following questions were presented in an earlier blog (the questions are reproduced here) along with solutions. Please compare your attempts/partial attempts too are to be compared…that is the way to learn:

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 in 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 squares 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 squares 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 T, 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 triple (a,b,c) in T, the triple (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-a)(7-b)(7-c).

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 math 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 weight lifters in S, 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 2 points as no one is all three (swimmer, cyclist and weight lifter). 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 would be 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.)

Problem 4:

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 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 4:

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 having a black cap and B must be wearing a black cap as observed by C. But then B must observe a 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 also 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: A: white cap; B: white cap; C:black cap; D:white cap; E: black cap.

Problem 5:

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}(i)=f(i) for each i \in A. Here f^{M} denotes the composite function f \circ f \circ \ldots \circ f repeated M times.

Solution 5:

Let us recall the following properties of a bijective function:

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} = f = I_{A} \circ f

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

d) If f, g, h are bijective functions from A to A 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 at hand, since A has n elements, we see that the 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 function in the sequence:

f^{2}, 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 and n, m > n, say, we must have f^{m}=f^{n}

If n=1, we take 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 with M>1. Note that this means f^{M}(i)=f(i) for all i \in A. QED.

Problem 6:

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.

Solution 6:

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

Since the sum of all angles of a hexagon is equal to (6-2) \times 180=720 \deg, it follows that each interior angle must be equal to 720/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. We use the vector method: 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}=(d\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, 60 degrees, 120 degrees, 180 degrees, 240 degrees, 300 degrees respectively.

Since the sum of all these six vectors is \overline{0}, it implies 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

(a,b)=(2,5), (a,e)=(3,4), c=6….(i)

(a,b)=(5,6), (a,e)=(4,5), c=2…(ii)

(a,b)=(2,6), (a,e)=(5,5), c=4…(iii)

The possibility that (a,b)=(3,4), (a,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

Case (iv):

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: Embed the hexagon in an appropriate equilateral triangle, whose sides consist of some sides of the hexagon.

Solutions to the remaining problems from that blog will have to be tried by the student. 

Cheers,

Nalin Pithwa.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.