INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More 

March 11, 2021

INMO 2021 Question No. 1 Solution

Suppose $r\geq 2$ is an integer, and let $m_{1},n_{1},m_{2},n_{2} \cdots ,m_{r},n_{r}$ be $2r$ integers such that
$$|m_{i}n_{j}−m_{j}n_{i}|=1$$
for any two integers $i$ and $j$ satisfying $1\leq i <j <r$. Determine the maximum possible value of $r$.

Solution:

Let us consider the case for $r =2$.

Then $|m_{1}n_{2} - m_{2}n_{1}| =1$.......(1)

Let us take $m_{1} =1, n_{2} =1, m_{2} =0, n_{1} =0$. Then, clearly the condition holds for $r =2$.

Now, let us check the case for $r =3$. Then if the conditions were to hold then, we should have, $$i =1, j =2,3$$

$$i =2, j =3$$

Then,

$$| m_{1} n_{2}-m_{2} n_{1}| =1\cdots(2) \\|m_{1} n_{3}-m_{3} n_{1}| =1 \cdots(3) \\ |m_{2} n_{3} - m_{3} n_{2}| =1 \cdots(4)$$ respectively.

Then, let us try to choose the value of $m_{1},n_{1}; m_{2},n_{2}; m_{3},n_{3}$ such that the conditions (2) ,(3) and (4) holds.

Then, let us take $m_{1} =1,n_{2}=1,m_{2}=0,n_{1}=0,m_{3}=1,n_{3}=1,m_{3} =1,n_{3} =0$ respectively.

Therefore the results holds for $r =3$.

Now, let us consider the case where $r\geq 4$

Let $c_{i}$ and $d_{i}$ be the remainders when $m_{i}$ and $n_{i}$ are divided by $2$ respectively, that is,

$c_{i} \equiv m_{i}$ (mod 2), and $d_{i} \equiv n_{i}$ (mod 2)

Therefore $c_{i}, d_{i} \in \{0,1\}$, since these are the only possible remainders when something is divided by $2$.

Now, the parities of both $m_{i}$ and $n_{i}$ cannot be the even , as in that case for any $j$, we have, $$|m_{i} n_{j} - m_{j} n_{i}| \neq 1$$, as it would be clearly even.

therefore, the possible values of the orderes pair $(c_{i},d_{i})$ would be $(0,1), (1,0)$ or $(1,1)$ respectively.

now, we see that if the parity patterns of $(m_{i},n_{i})$ and $(m_{j},n_{j})$ be the same, that is the parities of $m_{i}$ and $m_{j}$ ; $n_{i}$ and $n_{j}$ are the same, then,

$$ |m_{i} n_{j} - m_{j}n_{i}| = \text{ even } \neq 1$$

Therefore , the parity patterns of two pairs cannot be same.

Now, there are $4$ pairs $(m_{1}, n_{1}); (m_{2}, n_{2}) ; (m_{3}, n_{3})$ and $(m_{4}, n_{4})$ respectively.

therefore by pigeon hole principle at last two of these four pairs should have the same parity pattern, leading to a contradiction that we just discussed.

Therefore the conditions are not satisfied for $r =4$.

Therefore the maximum value of $r$ would be $3$.

Leave a Reply

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

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
enter