How Cheenta works to ensure student success?

Explore the Back-StorySuppose $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$.

Cheenta is a knowledge partner of Aditya Birla Education Academy

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIALAcademic Programs

Free Resources

Why Cheenta?

Online Live Classroom Programs

Online Self Paced Programs [*New]

Past Papers

More