# More PreRMO or PRMO practice questions 2019

1. Find the remainder when $37^{100}$ is divided by 29.
2. Compute the last two digits of $9^{1500}$.
3. Prove for any integers a and b that $a^{2}+b^{2}$ never leaves a remainder of 3 when divided by 4.
4. Prove that the equation $a^{2}+b^{3}=3c^{2}$ has no solutions in non zero integers a, b and c.
5. Prove that the square of any odd integer always leaves a remainder of 1 when divided by 8.

More later,

Nalin Pithwa

# Pre RMO practice 2019

1) Determine whether the following functions are well-defined:

1a) $f: Q \rightarrow Z$ defined by $f(a/b)=a$

1b) $f: Q \rightarrow Q$ defined by $f(a/b)=a^{2}/b^{2}$

2) Determine whether the function $f: R^{+} \rightarrow Z$ defined by mapping a real number r to the first digit to the right of the decimal point in a decimal expansion of r is well-defined.

3) Apply the Euclidean algorithm to obtain GCD of $(57970,10353)$ and express it as a linear combination of 57970 and 10353.

4) For each of the following pairs of integers a and b, determine their greatest common divisor, their least common multiple, and write their greatest common divisor in the form $ax+by$ for some integers x and y.

(a) a=20, b=13

(b) a=69, b=372

(c) a=792, b=275

(d) a=11391, b=5673

(e) a=1761, b=1567

(f) a=507885, b=60808

5) Prove that if the integer k divides the integers a and b then k divides $as+bt$ for every pair of integers s and t.

6) Prove that if n is composite then there are integers a and b such that a divides ab but n does not divide either a or b.

7) Let a, b and N be fixed integers with a and b non-zero and let $d= (a,b)$ be the greatest common divisor of a and b. Suppose $x_{0}$ and $y_{0}$ are particular solutions to $ax+by=N$. Prove for any integer r that integers $x=x_{0}+\frac{b}{d}t$ and $y=y_{0}-\frac{a}{d}t$ are also solutions to $ax+by=N$ (this is in fact the general solution).

8) Determine the value $\phi(n)$ for each integer $n \leq 30$ where $\phi$ denotes the Euler-$\phi$ function.

9) Prove the Well-Ordering Property of integers by induction and prove the minimal element is unique.

10) If p is a prime prove that there do not exist non-zero integers a and b such that $a^{2}=pb^{2}$ (that is, $\sqrt{p}$ is not a rational number).

11) Let p be a prime and $n \in Z^{+}$. Find a formula for the largest power of p which divides $n!$ (it involves the greatest integer function).

12) Prove for any given positive integer N there exist only finitely many integers n with $\phi(n)=N$ where $\phi$ denotes Euler’s $\phi$-function.

13) Prove that if d divides n then $latex \phi(d)$ divides $\phi(n)$ where $\phi$ denotes Euler’s $\phi$-function.

More later,

Hope this gives you some math meal to churn for the Pre RMO or PRMO or even the ensuing RMO of Homi Bhabha Science Foundation.

Regards,

Nalin Pithwa

# Pre-RMO training; a statement and its converse; logic and plane geometry

I hope the following explanation is illuminating to my readers/students:

How to prove that two lines are parallel ? (Note that we talk of parallel lines only when they lie in the same plane; on the other hand: consider the following scenario — your study table and the floor on which it stands. Let us say you draw a straight line AB on your study table and another line PQ on the floor on which the study table is standing; then, even though lines AB and PQ never meet, we do not say that they are parallel because they lie in different planes. Such lines are called skew lines. They are dealt with in solid geometry or 3D geometry or vector spaces).

Coming back to the question — when can we say that two lines are parallel?

Suppose that a transversal crosses two other lines.

1) If the corresponding angles are equal, then the lines are parallel.
2) If the alternate angles are equal, then the lines are parallel.
3) If the co-interior angles are supplementary, then the lines are parallel.

A STATEMENT AND ITS CONVERSE

Let us first consider the following statements:

A transversal is a line that crosses two other lines. If the lines crossed by a transversal are parallel, then the corresponding angles are equal; if the lines crossed by a transversal are parallel, then the alternate interior angles are equal; if the lines crossed by a transversal are parallel, then the co-interior angles are supplementary.

The statements given below are the converses of the statement given in the above paragraph; meaning that they are formed from the former statements by reversing the logic. For example:

STATEMENT: If the lines are parallel then the corresponding angles are equal.

CONVERSE: If the corresponding angles are equal, then the lines are parallel.

Pairs such as these, a statement and its converse, occur routinely through out mathematics, and are particularly prominent in geometry. In this case, both the statement and its converse are true. It is important to realize that a statement and its converse are, in general, quite different. NEVER ASSUME THAT BECAUSE A STATEMENT IS TRUE, SO ITS CONVERSE IS ALSO TRUE. For example, consider the following:

STATEMENT: If a number is a multiple of 4, then it is even.
CONVERSE: If a number is even, then it is a multiple of 4.

The first statement is clearly true. But, let us consider the number 18. It is even. But 18 is not a multiple of 4. So, the converse is not true always.

$\it Here \hspace{0.1in} is \hspace{0.1in}an \hspace {0.1in}example \hspace{0.1in}from \hspace{0.1in}surfing$

STATEMENT: If you catch a wave, then you will be happy.
CONVERSE: If you are happy, then you will catch a wave.

Many people would agree with the first statement, but everyone knows that its converse is plain silly — you need skill to catch waves.

Thus, the truth of a statement has little to do with its converse. Separate justifications (proofs) are required for the converse and its statements.

Regards,
Nalin Pithwa.

Reference: (I found the above beautiful, simple, lucid explanation in the following text): ICE-EM, year 7, book 1; The University of Melbourne, Australian Curriculum, Garth Gaudry et al.

# Pre RMO Training: Plane geometry with combinatorics

Question 1:

There are 4 possible ways to place three distinct lines in a plane. Two of these configurations involve parallel lines, the other two do not. Draw all these possibilities including the one which encloses a region.

Question 2:

Prove that the sum of any two sides of a triangle is greater than the third side. Hint: Use the following permissible clever argument: the shortest distance joining any two distinct points is given by a straight line joining those two points.

Question 3:

There are 8 possible ways to place 4 distinct lines in a plane. Five of these configurations involve parallel lines; the other three do not. Draw all the possibilities.

Remark: Questions like 1 and 2 are at the heart of combinatorics questions in plane geometry in pre RMO and RMO.

Cheers,
Nalin Pithwa

PS: Prove the parallelogram law: $|a+b| \leq |a|+|b|$

# Tutorial problems for RMO 2019 : combinatorics continued

1) In how many ways can 5 men and 5 women be seated in a round table if no two women may be seated side by side?

2) Six generals propose locking a safe containing top secret with a number of different locks. Each general will be given keys to certain of these locks. How many locks are required and how many keys must each general have so that, unless at least four generals are present, the safe cannot be opened?

3) How many integers between 1000 and 9999 inclusive have distinct digits? Of these, how many are even numbers? How many consist entirely of odd digits?

4) In how many ways can 9 distinct objects be placed in 5 distinct boxes in such a way that 3 of these boxes would be occupied and 2 would be empty?

5) In how many permutations of the word AUROBIND do the vowels appear in the alphabetical order?

6) There is an unlimited supply of weights of integral numbers of grams. Using n or fewer weights, find the number of ways in which a weight of m grams can be obtained. Prove that there is a bijection of the set of all such ways on the set of increasing words of length $(n-1)$ or $(m+1)$ ordered letters.

7) How many distinct solutions are there of $x+y+z+w=10$ (a) in positive integers and (b) in non-negative integers?

8) A train with n passengers aboard makes m stops. In how many ways can the passengers distribute themselves among these m stops as alighting passengers? if we are concerned only with the number of alighting passengers at each stop, how would the answer be modified?

9) There are 16 books on a bookshelf. In how many ways can 6 of these books be selected if a selection must not include two neighbouring books?

10) Show that there are ${(n=5)} \choose 5$ distinct throws of a throw with n non-distinct dice.

11) Given n indistinguishable objects and n additional distinct objects —- also distinct from the earlier n objects — in how many ways can we choose n out of the 2n objects?

12) Establish the following relations:
12a) $B_{n+1}=\sum_{k=0}^{n}(B_{k}){n \choose k}$
12b) $\sum_{k}{p \choose k}{q \choose {n-k}}={{p+q} \choose n}$
12c) $S_{n+1}^{m} = \sum_{k=0}^{n}{n \choose k}S_{k}^{m-1}$
12d) $n^{p}=\sum_{k=0}^{n}{n \choose k}k! (S_{p}^{k})$

13) Prove the following identity for all real numbers x:
$x^{n}= \sum_{k=1}^{n}S_{n}^{k}[x]_{k}$

14) Express $x^{4}$ in terms of ${x \choose 4}$, ${x \choose 3}$, …by using the $S_{n}^{k}$‘s. Express ${x \choose 4}$ in terms of $x^{4}$, $x^{3}$, …by using the $s_{n}^{k}$‘s.

15) A circular loop is divided into p parts, p prime. In how many ways can we paint the loop with n colours if we do not distinguish between patterns which differ only by a rotation of the loop? Deduce Fermat’s Little theorem: $n^{p}-n$ is divisible by p if p is prime.

16) In problem 15, prove that $n^{p}-n$ is also divisible by 2p if $p \neq 2$. Where is the hypothesis that p is prime used in Problem 15 or in this problem?

17) How many equivalence relations are possible on an n-set?

18) The complete homogeneous symmetric function of n variables $\alpha_{1}$, $\alpha_{2}$, $\ldots$, $\alpha_{n}$ of degree r is defined as $h_{r}(\alpha_{1},\alpha_{2}, \alpha_{3}, \ldots, \alpha_{n})=\sum \alpha_{1}^{i_{1}}\alpha_{2}^{i_{2}}\ldots \alpha_{n}^{i_{n}}$ the summation being taken over all ordered partitions of r, where the parts are also allowed to be zero. How many terms are there in $h_{r}$?

Test yourself ! Improve your mettle in math !
Regards,
Nalin Pithwa.