Cheenta
How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

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$.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

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