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