Miscellaneous questions: part II: solutions to tutorial practice for preRMO and RMO

Refer the blog questions a few days before:

Question 1:

Let a_{1}, a_{2}, \ldots, a_{10} be ten real numbers such that each is greater than 1 and less than 55. Prove that there are three among the given numbers which form the lengths of the sides of a triangle.

Answer 1:

Without loss of generality, we may take 1<a_{1}\leq a_{2}\leq \ldots \leq a_{10}<55…..call this relation (i).

Let, if possible, no three of the given numbers be the lengths of the sides of a triangle. (That is, no three satisfy the triangle inequality. Note that when we say three numbers a, b and c satisfy the triangle inequality —- it means all the following three inequalities have to hold simultaneously: a+b>c, a+c>b and b+c>a). We will consider triplets a_{i}, a_{i+1}, a_{i+2} and 1 \leq i \leq 8. As these numbers do not form the lengths of the sides of a triangle, the sum of the smallest two numbers should not exceed the largest number, that is, a_{i}+a_{i+1} \leq a_{i+2}. Hence, we get the following set of inequalities:

i=1 gives a_{1}+a_{2} \leq a_{3} giving 2 < a_{3}.

i=2 gives a_{2}+a_{3} \leq a_{4} giving 3 < a_{4}

i=3 gives a_{3}+a_{4} \leq a_{5} giving 5 < a_{5}

i=4 gives a_{4}+a_{5} \leq a_{6} giving 8 < a_{6}

i=5 gives a_{5}+a_{6} \leq a_{7} giving 13 < a_{7}

i=6 gives a_{6}+a_{7} \leq a_{8} giving 21 < a_{8}

i=7 gives a_{7}+a_{8} \leq a_{9} giving 34 < a_{9}

i=8 gives a_{8}+a_{9} \leq a_{10} giving 55<a_{10}

contradicting the basic hypothesis. Hence, there exists three numbers among the given numbers which form the lengths of the sides of a triangle.

Question 2:

In a collection of 1234 persons, any two persons are mutual friends or enemies. Each person has at most 3 enemies. Prove that it is possible to divide the collection into two parts such that each person has at most 1 enemy in his sub-collection.

Answer 2:

Let C denote the collection of given 1234 persons. Let \{ C_{1}, C_{2}\} be a partition of C. Let e(C_{1}) denote the total number of enemy pairs in C_{1}. Let e(C_{2}) denote the total number of enemy pairs in C_{2}.

Let e(C_{1}, C_{2})= e(C_{1})+e(C_{2}) denote the total number of enemy pairs corresponding to the partition \{ C_{1}, C_{2}\} of C. Note e(C_{1}, C_{2}) is an integer greater than or equal to zero. Hence, by Well-Ordering Principle, there exists a partition having the least value of e(C_{1}, C_{2}).

Claim: This is “the” required partition.

Proof: If not, without loss of generality, suppose there is a person P in C_{1} having at least 2 enemies in C_{1}. Construct a new partition \{D_{1}, D_{2}\} of C as follows: D_{1}=C_{1}-\{ P \} and D_{2}=C_{2}- \{P\}. Now, e(D_{1}, D_{2})=e(D_{1})+e(D_{2}) \leq \{ e(C_{1})-2\} + \{ e(C_{2})+1\}=e(C_{1}, C_{2})-1. Hence, e(D_{1}, D_{2})<e(C_{1}, C_{2}) contradicting the minimality of e(C_{1}, C_{2}). QED.

Problem 3:

A barrel contains 2n balls, numbered 1 to 2n. Choose three balls at random, one after the other, and with the balls replaced after each draw.

What is the probability that the three element sequence obtained has the properties that the smallest element is odd and that only the smallest element, if any is repeated?

Answer 3:

The total number of possible outcomes is N=2n \times 2n \times 2n=8n^{3}. To find the total number of favourable outcomes we proceed as follows:

Let a be any odd integer such that 1 \leq a \leq 2n-1 and let us count the sequences having a as least element.

(i) There is only one sequence (a,a,a) with a repeated thrice.

(ii) There are 2n-a sequences of the form (a,a,b) with a<b \leq 2n. For each such sequence there are three distinct permutations possible. Hence, there are in all 3(2n-a) sequences with a repeated twice.

iii) When n>1, for values of a satisfying 1 \leq a \leq (2n-3), sequences of the form (a,b,c,) with a<b<c \leq 2n are possible and the number of such sequences is r=1+2+3+\ldots+(2n+a-1)=\frac{1}{2}(2n-a)(2n-a-1). For each such sequence, there are six distinct permutations possible. Hence, there are 6r=3(2n-a)(2n-a-1) sequences in this case.

Hence, for odd values of a between 1 and 2n-1, the total counts of possibilities S_{1}, S_{2}, S_{3} in the above cases are respectively.

S_{1}=1+1+1+\ldots+1=n

S_{2}=3(1+3+5+\ldots+(2n-1))=3n^{2}

3(2 \times 3 + 4 \times 5 + \ldots+ (2n-2)(2n-1))=n(n-1)(4n+1).

Hence, the total number A of favourable outcomes is A=S_{1}+S_{2}+S_{3}=n+3n^{2}+n(n-1)(4n+1)=4n^{3}. Hence, the required probability is \frac{A}{N} = \frac{4n^{3}}{8n^{3}} = \frac{1}{2}. QED>

Cheers,

Nalin Pithwa

 

 

 

 

 

 

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.

 

Miscellaneous questions: part II: tutorial practice for preRMO and RMO

Problem 1:

Let a_{1}, a_{2}, \ldots, a_{10} be ten real numbers such that each is greater than 1 and less than 55. Prove that there are three among the given numbers which form the lengths of the sides of a triangle.

Problem 2:

In a collection of 1234 persons, any two persons are mutual friends or enemies. Each person has at most 3 enemies. Prove that it is possible to divide this collection into two parts such that each person has at most 1 enemy in his subcollection.

Problem 3:

A barrel contains 2n balls numbered 1 to 2n. Choose three balls at random, one after the other, and with the balls replaced after each draw. What is the probability that the three element sequence obtained has the properties that the smallest element is odd and that only the smallest element, if any, is repeated?

That’s all, folks !!

You will need to churn a lot…!! In other words, learn to brood now…learn to think for a long time on a single hard problem …

Regards,
Nalin Pithwa

Miscellaneous questions: Part I: tutorial practice for preRMO and RMO

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 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 sixty four entries are in fact equal.

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 I. Prove that the sum is divisible by 7.

Problem 3:

In a class of 25 students, there are 17 cyclists, 13 swimmers, and 8 weight lifters and no one in 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.

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.

Problem 5:

Let f be a bijective (one-one and onto) 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. Note that f^{M} denotes the composite function f \circ f \circ f \ldots \circ f repeated M times.

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.

Problem 7:

There are ten objects with total weights 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 pans of a balance.

Problem 8:

In 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 writtein down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that this final sum is zero?

Problem 9:

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.

Try these !!

Regards,
Nalin Pithwa

Find a flaw in this proof: RMO and PRMO tutorial

What ails the following proof that all the elements of a finite set are equal?

The following is the “proof”;

All elements of a set with no elements are equal, so make the induction assumption that any set with n elements has all its elements equal. In a set with n elements, the first and the last n are equal by induction assumption. They overlap at n, so all are equal, completing the induction.

End of “proof:

Regards,

Nalin Pithwa

Concept of order in math and real world

  1. Rise and Shine algorithm: This is crazy-sounding, but quite a perfect example of the need for “order” in the real-world: when we get up in the morning, we first clean our teeth, finish all other ablutions, then go to the bathroom and first we have to remove our pyjamas/pajamas and then the shirt, and then enter the shower; we do not first enter the shower and then remove the pyjamas/shirt !! 🙂
  2. On the number line, as we go from left to right: a<x<b, that is any real number to the left of another real number is always “less than” the number to the right. (note that whereas the real numbers form an “ordered field”, the complex numbers are only “partially ordered”…we will continue this further discussion later) .
  3. Dictionary order
  4. Alphabetical order (the letters A \hspace{0.1in} B \ldots Z in English.
  5. Telephone directory order
  6. So a service like JustDial certainly uses “order” quite intensely: let us say that you want to find the telephone clinic landline number of Dr Mrs Prasad in Jayanagar 4th Block, Bengaluru : We first narrow JustDial to “Location” (Jayanagar 4th Block, Bengaluru), then narrow to “doctors/surgeons” as the case may be, and then check in alphabetic order, the name of Dr Mrs Prasad. So, we clearly see that the “concept” and “actual implementation” of order (in databases) actually speeds up so much the time to find the exact information we want.
  7. So also, in math, we have the concept of ordered pair; in Cartesian geometry, (a,b) means that the first component a \in X-axis and b \in Y-axis. This order is generalized to complex numbers in the complex plane or Argand’s diagram.
  8. There is “order” in human “relations” also: let us (x,y) represents x (as father) and y (as son). Clearly, the father is “first” and the son is “second”.
  9. So, also any “tree” has a “natural order”: seed first, then roots, then branches.

Regards,

Nalin Pithwa.

Why do we need proofs? In other words, difference between a mathematician, physicist and a layman

Yes, I think it is a very nice question, which kids ask me. Why do we need proofs? Well, here is a detailed explanation (I am not mentioning the reference I use here lest it may intimidate my young enthusiastic, hard working students or readers. In other words, the explanation is not my own; I do not claim credit for this…In other words, I am just sharing what I am reading in the book…)

Here it goes:

What exactly is the difference between a mathematician, a physicist, and a layman? Let us suppose that they all start measuring the angles of hundreds of triangles of various shapes, find the sum in each case and keep a record. Suppose the layman finds that with one or two exceptions, the sum in each case comes out to be 180 degrees. He will ignore the exceptions and say “the sum of the three angles in a triangle  is 180 degrees.” A physicist will be more cautious in dealing with the exceptional cases. He will examine them more carefully. If he finds that the sum in them is somewhere between 179 degrees to 180 degrees, say, then he will attribute the deviation to experimental errors. He will then state a law: The sum of three angles of any triangle is 180 degrees. He will then watch happily as the rest of the world puts his law to test and finds that it holds good in thousands of different cases, until somebody comes up with a triangle in which the law fails miserably. The physicist now has to withdraw his law altogether or else to replace it by some other law which holds good in all cases tried. Even this new law may have to be modified at a later date. And, this will continue without end.

A mathematician will be the fussiest of all. If there is even a single exception he will refrain from saying anything. Even when millions of triangles are tried without a single exception, he will not state it as a theorem that the sum of the three angles in ANY triangle is 180 degrees. The reason is that there are infinitely many different types of triangles. To generalize from a million to infinity is as baseless to a mathematician as to generalize from one to a million. He will at the most make a conjecture and say that there is a strong evidence suggesting that the conjecture is true. But that is not the same thing as a proving a theorem. The only proof acceptable to a mathematician is the one which follows from earlier theorems by sheer logical implications (that is, statements of the form : If P, then Q). For example, such a proof follows easily from the theorem that an external angle of a triangle is the sum of the other two internal angles.

The approach taken by the layman or the physicist is known as the inductive approach whereas the mathematician’s approach is called the deductive approach. In the former, we make a few observations and generalize. In the latter, we deduce from something which is already proven. Of course, a question can be raised as to on what basis this supporting theorem is proved. The answer will be some other theorem. But then the same question can be asked about the other theorem. Eventually, a stage is reached where a certain statement cannot be proved from any other earlier proved statement(s) and must, therefore, be taken for granted to be true. Such a statement is known as an axiom or a postulate. Each branch of math has its own axioms or postulates. For examples, one of the axioms of geometry is that through two distinct points, there passes exactly one line. The whole beautiful structure of geometry is based on 5 or 6 axioms such as this one. Every theorem in plane geometry or Euclid’s Geometry can be ultimately deduced from these axioms.

PS: One of the most famous American presidents, Abraham Lincoln had read, understood and solved all of Euclid’s books (The Elements) by burning mid-night oil, night after night, to “sharpen his mental faculties”. And, of course, there is another famous story (true story) of how Albert Einstein as a very young boy got completely “addicted” to math by reading Euclid’s proof of why three medians of a triangle are concurrent…(you can Google up, of course).

Regards,

Nalin Pithwa