Pre RMO August 2018: some practice problems selected

Question 1:

Can the product of 31256 and 8427 be 263395312? Give reasons (of course, brute force long calculation will not be counted as an answer ! :-)).

Solution 1:

Use the rule “casting out the nines”: a number divided by 9 will leave the same remainder as the sum of its digits divided by nine.

In this particular case, the sums of the digits of the multiplicand, multiplier, and product are 17, 21, and 34 respectively, again, the sums of the digits of these three numbers are 8, 3, and 7, hence, 8 times 3 is 24 and, which has 6 for the sum of the digits; thus, we have two different remainders, 6 and 7, and the multiplication is incorrect.

Question 2:

Prove that 4.41 is a square number in any scale of notation whose radix is greater than 4.

Solution 2:

Let r be the radix; then, 4.41 = 4 + \frac{4}{r} + \frac{1}{r^{2}}=(2 + \frac{1}{r})^{2};

thus, the given number is the square of 2.1

Question 3:

In what scale is the decimal number 2.4375 represented by 2.13?

Solution 3:

Let r be the radix; then, 2 + \frac{}{} + \frac{}{} = 2.4375= 2 \frac{7}{16}

hence, 7r^{2}-16r-48=0

that is, (7r+12)(r-4)=0.

Hence, the radix is 4.

More later,

Nalin Pithwa

Pre-RMO or RMO algebra practice problem: infinite product

Find the product of the following infinite number of terms:

\frac{7}{9} \times \frac{26}{28} \times \frac{63}{65} \times \ldots = \prod_{m=2}^{\infty}\frac{m^{3}-1}{m^{3}+1}

m^{3}-1=(m-1)(m^{2}+m+1), and also, m^{3}+1=(m+1)(m^{2}-m+1)=(m-1+2)((m-1)^{2}+(m-1)+1)

Hence, we get P_{m}=\frac{7}{9} \times \frac{26}{28} \times \frac{63}{65} \times \ldots \times \frac{m^{3}-1}{m^{3}+1}, which in turn, equals

(\frac{1}{3} \times \frac{7}{3}) \times (\frac{2}{4} \times \frac{13}{7}) \times (\frac{3}{5} \times \frac{21}{13})\times \ldots (\frac{m-1}{m+1} \times \frac{m^{2}+m+1}{m^{2}-m+1}), that is, in turn equal to

\frac{2}{3} \times \frac{m^{2}+m+1}{m(m+1)}, that is, in turn equal to

\frac{}{} \times (1+ \frac{1}{m(m+1)}), so that when m \rightarrow \infty, and then P_{m} \rightarrow 2/3.

personal comment: I did not find this solution within my imagination !!! ๐Ÿ™‚ ๐Ÿ™‚ ๐Ÿ™‚

The credit for the solution goes to “Popular Problems and Puzzles in Mathematics” by Asok Kumar Mallik, IISc Press, Foundation Books. Thanks Prof. Mallik !!

Cheers,

Nalin Pithwa

 

Algebra Training for RMO and Pre-RMO: let’s continue: Fibonacci Problem and solution

Fibonacci Problem:

Leonardo of Pisa (famous as Fibonacci) (1173) wrote a book “Liber Abaci” (1202), wherein he introduced Hindu-Arabic numerals in Europe. In 1225, Frederick II declared him as the greatest mathematician in Europe when he posed the following problem to defeat his opponents.

Question:

Determine the rational numbers x, y and z to satisfy the following equations:

x^{2}+5=y^{2} and x^{2}-5=z^{2}.

Solution:

Definition: Euler defined a congruent number to be a rational number that is the area of a right-angled triangle, which has rational sides. With p, q, and r as a Pythagorean triplet such that r^{2}=p^{2}+q^{2}, then \frac{pq}{2} is a congruent number.

It can be shown that square of a rational number cannot be a congruent number. In other words, there is no right-angled triangle with rational sides, which has an area as 1, or 4, or \frac{1}{4}, and so on.

Characteristics of a congruent number: A positive rational number n is a congruent number, if and only if there exists a rational number u such that u^{2}-n and u^{2}+n are the squares of rational numbers. (Thus, the puzzle will be solved if we can show that 5 is a congruent number and we can determine the rational number u(=x)). First, let us prove the characterisitic mentioned above.

Necessity: Suppose n is a congruent number. Then, for some rational number p, q, and r, we have r^{2}=p^{2}+q^{2} and \frac{pq}{2}=n. In that case,

\frac{p+q}{2}, \frac{p-q}{2} and n are rational numbers and we have

(\frac{p+q}{2})^{2}=\frac{p^{2}+q^{2}}{4}+\frac{pq}{2}=(\frac{r}{2})^{2}+n and similarly,

(\frac{p-q}{2})^{2}=(\frac{r}{2})^{2}-n.

Setting u=\frac{r}{2}, we get u^{2}-n and u^{2}+n are squares of rational numbers.

Sufficiency:

Suppose n and u are rational numbers such that \sqrt{u^{2}-n} and \sqrt{u^{2}+n} are rational, when

p=\sqrt{u^{2}+n}+\sqrt{u^{2}-n} and q=\sqrt{u^{2}+n}-\sqrt{u^{2}-n}

and 2n are rational numbers satisfying p^{2}+q^{2}=(2n)^{2} is a rational square and also \frac{pq}{2}=n, a rational number which is a congruent number.

So, we see that the Pythagorean triplets can lead our search for a congruent number. Sometimes a Pythagorean triplet can lead to more than one congruent number as can be seen with (9,40,41). This set obviously gives 180 as a congruent number. But, as 180=5 \times 36=5 \times 6^{2}, we can also consider a rational Pythagorean triplet (\frac{9}{6}, \frac{40}{6}, \frac{41}{6}), which gives a congruent number 5 (we were searching for this congruent number in this puzzle!). We also determine the corresponding u=\frac{r}{2}=\frac{41}{12}.

The puzzle/problem is now solved with x=\frac{41}{12}, which gives y=\frac{49}{12}, and z=\frac{31}{12}.

One can further show that if we take three rational squares in AP, u^{2}-n, and u^{2}, and u^{2}+n, with their product defined as a rational square v^{2} and n as a congruent number, then x=u^{2}, y=v is a rational point on the elliptic curve y^{2}=x^{3}-n^{2}x.

Reference:

1) Popular Problems and Puzzles in Mathematics: Asok Kumar Mallik, IISc Press, Foundation Books, Amazon India link:

https://www.amazon.in/Popular-Problems-Puzzles-Mathematics-Mallik/dp/938299386X/ref=sr_1_1?s=books&ie=UTF8&qid=1525099935&sr=1-1&keywords=popular+problems+and+puzzles+in+mathematics

2) Use the internet, or just Wikipedia to explore more information on Fibonacci Numbers, Golden Section, Golden Angle, Golden Rectangle and Golden spiral. You will be overjoyed to find relationships amongst all the mentioned “stuff”.

Cheers,

Nalin Pithwa

Solution to a RMO algebra practice question

Refer to question posted on blog of Mar 13 2018, reproduced here for your convenience. Compare your solution with the one given here:

Question:

Show that the following expression: [4-3x+\sqrt{16+9x^{2}-24x-x^{3}}]^{1/3}+[4-3x-\sqrt{16+9x^{2}-24x-x^{3}}]^{1/3} remains constant in the interval 0 \leq x \leq 1. Find this constant value.

Solution/proof:

Let y equal the given expression for x in the prescribed interval. Then, taking cube of both sides, we write

y^{3}=8-6x+3xy

y^{3}-8-3x(y-2)=0

(y-2)(y^{2}+2y+4-3x)=0

The only real value of y=2, a constant. The roots of the quadratic equation for 0<x<1 are complex. It is easy to check that y=2 for both x=0 and 1.

Alternately, derive the square roots of the expression within the radical; you can use the method of undetermined coefficients for this.

Cheers,

Nalin Pithwa.

 

Solutions to two algebra problems for RMO practice

Problem 1.

If a, b, c are non-negative real numbers such that (1+a)(1+b)(1+c)=8, then prove that the product abc cannot exceed 1.

Solution I:

Given that a \geq 0, b \geq 0, c \geq 0, so certainly abc>0, ab>0, bc>0, and ac>0.

Now, (1+a)(1+b) = 1 + a + b + ab and hence, (1+a)(1+b)(1+c) = (1+a+b+ab)(1+c)= 1+a+b+ab+c +ac + bc + abc=8, hence we get:

a+b+c+ab+bc+ca+abc=7.ย Clearly, the presence ofย a+b+c and abc reminds us of the AM-GM inequality.

Here it is AM \geq GM.

So, \frac{a+b+c}{3} \geq (abc)^{1/3}.

Also, we can say: \frac{ab+bc+ca}{3} \geq (ab.bc.ca)^{1/3}. Now, let x=(abc)^{1/3}.

So, 8 \geq 1+3x+3x^{2}+x^{3}

that is, 8 \geq (1+x)^{3}, or 2 \geq 1+x, that is, x \leq 1.ย So, this is a beautiful application of arithmetic mean-geometric mean inequality twice. ๐Ÿ™‚ ๐Ÿ™‚

Problem 2:

If a, b, c are three rational numbers, then prove that :\frac{1}{(a-b)^{2}} + \frac{1}{(b-c)^{2}} + \frac{1}{(c-a)^{2}} is always the square of a rational number.

Solution 2:

Let x=\frac{1}{a-b}, y=\frac{1}{b-c}, z=\frac{1}{c-a}. It can be very easily shown that \frac{1}{x}+ \frac{1}{y} + \frac{1}{z} =0, or xy+yz+zx=0. So, the given expression x^{2}+y^{2}+z^{2}=(x+y+z)^{2} is a perfect square !!!ย BINGO! ๐Ÿ™‚ ๐Ÿ™‚ ๐Ÿ™‚

Nalin Pithwa.

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/