Suppose $r \ge 2$ is an integer, and let $m_1, n_1, m_2, n_2, \dots, m_r, n_r$ be $2r$ integers such that $$\left|m_in_j-m_jn_i\right|=1$$for any two integers $i$ and $j$ satisfying $1 \le i<j \le r$. Determine the maximum possible value of $r$. Proposed by B Sury
Problem
Source: INMO 2021 Problem 1
Tags: number theory, INMO, Parity, Contradiction
07.03.2021 13:54
$r=3$? Parity seemed to be sufficient...
07.03.2021 13:56
Nice one Represent in Cartesian coordinates with $P_i=(m_i,n_i)$ to get area of $OP_i P_j=0.5$. I too got $r=3$, @above
Attachments:

07.03.2021 14:04
Deducted
07.03.2021 14:06
Mathematicsislovely wrote: Hope this works.... Maximum value of $r$ is 3. Let $P_i=(m_i,m_j)$.Then,$area(OP_iP_j)=1/2$. Then $P_iP_j||OP_1$,$i,j\ne 1$. So all other $P_j$ lie on a single line $||OP_1$ FTSOC there are 4 points. But then $OP_2P_3=1/2$,$OP_3O_4=1/2$ implies $OP_2P_4=1$ contradiction. Not 1, they lie on 2 lines
07.03.2021 14:10
mathsworm wrote: Mathematicsislovely wrote: Hope this works.... Maximum value of $r$ is 3. Let $P_i=(m_i,m_j)$.Then,$area(OP_iP_j)=1/2$. Then $P_iP_j||OP_1$,$i,j\ne 1$. So all other $P_j$ lie on a single line $||OP_1$ FTSOC there are 4 points. But then $OP_2P_3=1/2$,$OP_3O_4=1/2$ implies $OP_2P_4=1$ contradiction. Not 1, they lie on 2 lines I mean,$OP_1$ is a line and all other $P_i$ makes a line.
07.03.2021 14:10
The statement is very similiar to This. Ill edit in my solution soon. Lol the follow up is troll. Just note that we must have $$\binom{n}{2} = 2n - 3$$and so $n = 3$
07.03.2021 14:11
anantmudgal09 wrote: Suppose $r \ge 2$ is an integer, and let $m_1, n_1, m_2, n_2, \dots, m_r, n_r$ be $2r$ integers such that $$\left|m_in_j-m_jn_i\right|=1$$for any two integers $i$ and $j$ satisfying $1 \le i<j \le r$. Determine the maximum possible value of $r$. Proposed by B Sury Let $P_i$ be the points representing $(m_i, n_i)$, and define $f(P_i, P_j) = |m_i n_j - m_j n_i|$. Notice that by parity, we mustn't have any two coordinates $n_i, n_j$ such that both of them are even. Similarly, we couldn't have two coordinates such that $m_i, m_j$ are both even. Furthermore, if $P_i$ and $P_j$ are congruent modulo $2$. Then, $m_i n_j \equiv m_j n_i \ (\text{mod} \ 2)$, which is a contradiction. Therefore, we have $r \le 3$ (which is (O,O), (O,E), (E,O)), and is indeed possible by taking \[ (1,1), (0,1), (1,0) \]
07.03.2021 14:13
$(1,2), (2,3), (3,5)$ works as well.
07.03.2021 14:13
07.03.2021 14:19
Interpret as $r$ coordinates of $(m_i, n_i)$. By 2020 USOMO 4, the maximum number of pairs is $2r-3$, but since every pair must work, we have \[ 2r-3=\binom{r}{2} \implies r=2,3\]so $r=3$ is our maximum. To finish, a construction of $(0,1)$, $(1,0)$, and $(1,1)$ works.
07.03.2021 14:23
Nice...I couldn’t qualify for INMO but I’m getting 3 by pairity of m, n.
07.03.2021 14:25
Suppose $r=4$ is possible. Let $v_i=(1,m_i,n_i)$. They will be linearly dependent. Let $\sum c_iv_i=0$ with $c_i$ integers and not all even. Then we can choose three of them, say $c_1,c_2,c_3$ such that either $1$ or $3$ of them are odd. But $\sum_{i=1}^3c_i(v_i\times v_4)=0$ which is not possible bcoz x component will be odd. Edit: pretty unnecessary overkill...Much simpler parity argument also works....not even an rmo level problem....so disappointing ...smh
07.03.2021 14:44
Ninjasolver0201 wrote: $(1,2), (2,3), (3,5)$ works as well. Hmm I discovered $(1,2,1); (1,3,2)$ during the contest...
07.03.2021 15:05
anantmudgal09 wrote: Suppose $r \ge 2$ is an integer, and let $m_1, n_1, m_2, n_2, \dots, m_r, n_r$ be $2r$ integers such that $$\left|m_in_j-m_jn_i\right|=1$$for any two integers $i$ and $j$ satisfying $1 \le i<j \le r$. Determine the maximum possible value of $r$. Proposed by B Sury Php gives r <=4. If f(x) denotes parity of x, then (f(m_i), f(n_i)) must be unique ordered pair for all indices i or else contradiction is easy. So, if r=4, choose indices i, j such that (f(m_i), f(n_i)) =(even, even) and (f(m_j), f(n_j)) =(odd, even) and get parity contradiction implying r<=3. Construction easy
07.03.2021 15:36
here's another way, let $m_1,n_1,m_2,n_2$ be two of the pairs and x,y be another. Then we get four possible pairs of two equations in (x,y)(so $r \leq 6$)[Choose the $\pm 1$'s]. Then we get $(x,y)=(m_1+m_2,n_1+n_2),(m_1-m_2,n_1-n_2)$ and the negatives of these 2. it is easy to check that no two of these 4 can have a product $\pm 1$ [its either 0 or $\pm$ 2]. Thus we can have atmost one of these 4 and 3 is the ans.
07.03.2021 15:37
NumberX wrote: here's another way, let $m_1,n_1,m_2,n_2$ be two of the pairs and x,y be another. Then we get four possible pairs of two equations in (x,y)(so $r \leq 6$)[Choose the $\pm 1$'s]. Then we get $(x,y)=(m_1+m_2,n_1+n_2),(m_1-m_2,n_1-n_2)$ and the negatives of these 2. it is easy to check that no two of these 4 can have a product $\pm 1$ [its either 0 or $\pm$ 2]. Thus we can have atmost one of these 4 and 3 is the ans. I wrote this solution.. Thank you for confirming
07.03.2021 16:09
This was literally same as USAMO 2020 P4
07.03.2021 17:35
At first of all we should construct some points $P_i = (m_i,n_i)$ in the cartesian palne. And let $O$ be the origin . Then area of $\triangle OP_iP_j$ is clearly $\frac{1}{2}$ . (Just using the determinents) we have put $2r$ points in Cartesian plane as following . [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(8cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -1.1338271604938273, xmax = 1.1338271604938273, ymin = -0.6597530864197526, ymax = 0.6597530864197522; /* image dimensions */ pen ccqqqq = rgb(0.8,0,0); pen fuqqzz = rgb(0.9568627450980393,0,0.6); pen qqwuqq = rgb(0,0.39215686274509803,0); draw((0.03358024691358025,0.19555555555555512)--(-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003)--cycle, linewidth(2) + blue); draw((-0.2923456790123457,-0.0849382716049384)--(0.03358024691358025,0.19555555555555512)--(-0.2607407407407408,0.2864197530864192)--cycle, linewidth(2) + ccqqqq); draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003)--cycle, linewidth(2) + fuqqzz); draw((-0.2923456790123457,-0.0849382716049384)--(-0.5708641975308643,0.2587654320987649)--(-0.2607407407407408,0.2864197530864192)--cycle, linewidth(2)); draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,2.172246804777998,40.715486381229354)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + ccqqqq); draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,40.71548638122936,85.13548556223948)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + qqwuqq); draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,85.13548556223947,129.01940047523658)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + blue); /* draw figures */ draw((0.03358024691358025,0.19555555555555512)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + blue); draw((-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003), linewidth(2) + blue); draw((0.2804938271604938,-0.06320987654321003)--(0.03358024691358025,0.19555555555555512), linewidth(2) + blue); draw((-0.2923456790123457,-0.0849382716049384)--(0.03358024691358025,0.19555555555555512), linewidth(2) + ccqqqq); draw((0.03358024691358025,0.19555555555555512)--(-0.2607407407407408,0.2864197530864192), linewidth(2) + ccqqqq); draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + ccqqqq); draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + fuqqzz); draw((-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003), linewidth(2) + fuqqzz); draw((0.2804938271604938,-0.06320987654321003)--(-0.2607407407407408,0.2864197530864192), linewidth(2) + fuqqzz); draw((-0.2923456790123457,-0.0849382716049384)--(-0.5708641975308643,0.2587654320987649), linewidth(2)); draw((-0.5708641975308643,0.2587654320987649)--(-0.2607407407407408,0.2864197530864192), linewidth(2)); draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2)); /* dots and labels */ dot((-0.2923456790123457,-0.0849382716049384),dotstyle); label("$O$", (-0.2962962962962963,-0.1422222222222223), NE * labelscalefactor); dot((0.2804938271604938,-0.06320987654321003),dotstyle); label("$P_1$", (0.2883950617283951,-0.04345679012345697), NE * labelscalefactor); dot((0.03358024691358025,0.19555555555555512),dotstyle); label("$P_2$", (0.04148148148148148,0.2153086419753082), NE * labelscalefactor); dot((-0.2607407407407408,0.2864197530864192),dotstyle); label("$P_3$", (-0.2528395061728395,0.3061728395061723), NE * labelscalefactor); dot((-0.5708641975308643,0.2587654320987649),dotstyle); label("$P_4$", (-0.562962962962963,0.278518518518518), NE * labelscalefactor); label("$\alpha$", (-0.2271604938271605,-0.06518518518518535), NE * labelscalefactor,ccqqqq); label("$\beta$", (-0.2706172839506173,-0.015802469135802678), NE * labelscalefactor,qqwuqq); label("$\gamma$", (-0.33185185185185184,0.001975308641975082), NE * labelscalefactor,blue); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Let the lengths $ OP_1 =y , OP_2 =x , OP_3 =z , OP_4 =w$ . from the area condition we can write \[\frac{wy \sin (\alpha +\beta +\gamma )}{2} = \frac{zx\sin (\beta)}{2} = \frac{xy \sin (\alpha)}{2} = \frac{zy \sin (\alpha +\beta)}{2} = \frac{wz \sin \gamma )}{2} = \frac{1}{2}\] clearly we have \[ \sin \alpha =\frac{1}{xy} , \sin \beta = \frac{1}{zx} \cdots (1)\] Then the next condition \[zy\sin (\alpha +\beta)=1\cdots (2)\] from previous two episode we get \[z\cos \beta +y\cos \alpha =x\] we can conclude that we can make a triangle $\triangle ABC$ with area $\frac{1}{2}$ and sides are $x,y,z$ respectively . as following [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -1.1338271604938273, xmax = 1.1338271604938273, ymin = -0.6597530864197526, ymax = 0.6597530864197522; /* image dimensions */ pen zzttff = rgb(0.6,0.2,1); pen qqwuqq = rgb(0,0.39215686274509803,0); pen zzttqq = rgb(0.6,0.2,0); draw((-0.3851851851851852,0.2449382716049378)--(-0.5570370370370371,-0.12839506172839515)--(0.03753086419753081,-0.1501234567901235)--cycle, linewidth(2) + blue); draw(arc((0.03753086419753081,-0.1501234567901235),0.05925925925925927,136.93680038622105,177.90706569471186)--(0.03753086419753081,-0.1501234567901235)--cycle, linewidth(2) + zzttff); draw(arc((-0.5570370370370371,-0.12839506172839515),0.05925925925925927,-2.092934305288143,65.28255908891657)--(-0.5570370370370371,-0.12839506172839515)--cycle, linewidth(2) + qqwuqq); draw(arc((-0.3851851851851852,0.2449382716049378),0.05925925925925927,-114.71744091108341,-43.06319961377892)--(-0.3851851851851852,0.2449382716049378)--cycle, linewidth(2) + zzttqq); /* draw figures */ draw((-0.3851851851851852,0.2449382716049378)--(-0.5570370370370371,-0.12839506172839515), linewidth(2) + blue); draw((-0.5570370370370371,-0.12839506172839515)--(0.03753086419753081,-0.1501234567901235), linewidth(2) + blue); draw((0.03753086419753081,-0.1501234567901235)--(-0.3851851851851852,0.2449382716049378), linewidth(2) + blue); /* dots and labels */ dot((-0.3851851851851852,0.2449382716049378),dotstyle); label("$A$", (-0.377283950617284,0.26469135802469085), NE * labelscalefactor); dot((-0.5570370370370371,-0.12839506172839515),dotstyle); label("$B$", (-0.6123456790123457,-0.09086419753086432), NE * labelscalefactor); dot((0.03753086419753081,-0.1501234567901235),dotstyle); label("$C$", (0.0454320987654321,-0.13037037037037044), NE * labelscalefactor); label("$Z$", (-0.5155555555555555,0.07901234567901204), NE * labelscalefactor); label("$X$", (-0.2607407407407408,-0.18962962962962965), NE * labelscalefactor); label("$Y$", (-0.15407407407407409,0.0711111111111108), NE * labelscalefactor); label("$\alpha$", (-0.0671604938271605,-0.12246913580246922), NE * labelscalefactor,zzttff); label("$\beta$", (-0.4938271604938272,-0.09481481481481494), NE * labelscalefactor,qqwuqq); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] clearly the angle $\angle BAC =\alpha +\beta $ so , $\alpha +\beta =90^{\circ}$. How, ever if 4 points could exist then we must have $\alpha +\beta +\gamma =90^{\circ}$ which means $\gamma =0^{\circ}$. So , only three point could exist . And they are $(1,1),(0,1),(1,0)$ . so , $r=3$
07.03.2021 18:03
Note that $\gcd(m_in_j,m_jn_i)=\gcd(m_in_j,m_jn_i-m_in_j)=1 \implies$ at most one of $m_i$ and $n_j$ is even for all $i,j$. Clearly, for $r=3$, $(m_1,n_1,m_2,n_2,m_3,n_3)=(0,1,-1,0,1,-1)$ works. Now, for the sake of contradiction, say $r \geq 4$ works. As $m_1n_2-m_2n_1$ is odd, at least one of $m_1,m_2,n_1,n_2$ is even. WLOG, say $m_1$ is even. Similarly, one of $m_2,n_2,m_3,n_3$ is even. As $m_2,m_3$ can't be even, WLOG say $n_2$ is even. But now, as $m_3n_4-m_4n_3$ is odd but none of $m_3,m_4,n_3,n_4$ can be even $\implies$ Contradiction. Hence, $r=3$ is the maximum value of $r$ that works.
07.03.2021 18:14
Observe that there is at most one $m_i$ which is even and at most one $n_j$ which is even. If $r \ge 4$, there exist two indices $k_1, k_2$, such that $m_{k_1}, n_{k_1}, m_{k_2}, n_{k_2}$ are all odd, and we have that $m_{k_1} n_{k_2} - m_{k_2} n_{k_1}$ is even; it's absolute value cannot be $1$. For construction, take $(1, 1), (1, 2), (2, 3)$
07.03.2021 18:49
anantmudgal09 wrote: Suppose $r \ge 2$ is an integer, and let $m_1, n_1, m_2, n_2, \dots, m_r, n_r$ be $2r$ integers such that $$\left|m_in_j-m_jn_i\right|=1$$for any two integers $i$ and $j$ satisfying $1 \le i<j \le r$. Determine the maximum possible value of $r$. Proposed by B Sury Just saw the problem, I am sure my solution is pretty similar to every other solution but here goes. The first part of the solution is to show that $r < 4$. The relation $\left|m_in_j-m_jn_i\right|=1$ means that no two of the $\{m_i\}_{1\leq i\leq r}$ or $\{n_j\}_{1\leq j\leq r}$ are even, else the corresponding $\left|m_in_j-m_jn_i\right|$ is even, hence cannot be $1$. Thus, atleast $(r-1)$ of the $\{m_i\}_{1\leq i\leq r}$ and $(r-1)$ of the $\{n_j\}_{1\leq j\leq r}$ are odd $\implies$ $(r-2)$ of the pairs $(m_i, n_i)_{1\leq i\leq r}$ are odd. WLOG, assume that all pairs $(m_i, n_i)$ are odd for $i > 2$. Clearly if $r >= 4$, then $(m_3, n_3)$ and $(m_4, n_4)$ are odd $\implies \left|m_3n_4-m_4n_3\right|$ is even, which is a contradiction. Thus, $r < 4$. For $r=3$, a simple construction like $$\begin{bmatrix} m_1 & m_2 & m_3\\ n_1 & n_2 & n_3 \end{bmatrix} = \begin{bmatrix} 1 & 3 & 4\\ 2 & 5 & 7 \end{bmatrix}$$does the job. Hence $r=3$ is the required answer.
07.03.2021 19:58
weirdly, I didn't think of parity at all. I assumed $n_i \neq 0$ for all $i$ (the case where some $n_i=0$ is easy). Assume $\frac{m_i}{n_i}$ to be ascendingly sorted in that order, and assume $n_i>0$ for all $i$ (cause we can change the sign of both $m_i$ and $n_i$), all WLOG. Then we have for all $i<j<k$, $$ \frac{1}{n_in_k} = \frac{m_k}{n_k}- \frac{m_i}{n_i} = \frac{m_k}{n_k}- \frac{m_j}{n_j} + \frac{m_j}{n_j}- \frac{m_i}{n_i} = \frac{1}{n_jn_k}+\frac 1{n_in_j}$$so $n_j = n_i + n_k$ for all $i<j<k$. But that is absurd if $r \ge 4$, as we get $n_2=n_1+n_4$ and $n_3=n_1+n_4$, and $n_2=n_1+n_3$, which gives $n_1=0$. Edit: For the sake of completeness I'll show what happens when $n_1=0$. Then $|m_1n_i|=1$ for all $i \ge 2$. Again, WLOG, we can assume $n_i > 0$ for all $i \ne 1$. Then each $n_i$ must be $1$. So $|m_2-m_3|=|m_2-m_4|=|m_3-m_4| = 1$, which is absurd.
07.03.2021 20:34
Want to say this here- (courtesy of CantonMathGuy) Any solution that uses USAMO 2020 4 might be inherently wrong. That question(and consequently the 2n-3 bound) requires all pairs to be composed of non-negative integers, which is not guaranteed here in the INMO problem.
08.03.2021 12:46
Not very different from the first geometric solution in this thread: 1. Clearly if pairs $(m_i,n_i)$ and $(m_j,n_j)$ work, then the triangle formed by these two pairs and the origin has area $\frac{1}{2}$. 2. Also, clearly $r = 2,3$ work. 3. Say $r \ge 4$. Then consider a quad $ABCD$ that is part of this polygon. It must be that $B$, $C$, and $D$ lie at an equal distance from $OA$. By PHP, two of these three points lie on the same side of $OA$. WLOG assume, $B$ and $C$ are these points. Then $OABC$ is a parallelogram. If we repeat this same argument for $OB$, we get that $D$ must lie on the same side of $OB$( and at the same distance from $OB$ as well) as one of $A$ or $C$, forming a parallelogram. Say $A$. Then $OBDA$ is a parallelogram. As $D$ does not lie on $AB$, $ODC$ and $OBC$(and hence $OAC$ as well) cannot have the same area. Contradiction.
08.03.2021 14:52
https://youtu.be/F-khVvpeHqc
09.03.2021 19:37
A different solution not using parity, it is a bit longer: If $r \ge 4 $, we know that $m_1n_i - m_in_1 = \pm 1$ for any $i$, by pigeonhole theorem, two of them must have the same value. WLOG (subject to reordering), we have $m_1n_2 - m_2n_1 = m_1n_3 - m_3n_1$ hence $m_1(n_2-n_3) = n_1(m_2-m_3)$. Note that $m_1$ and $n_1$ are coprime, there is $k \in \mathbb{N}$ such that $(n_2-n_3) = k n_1$ and $m_2-m_3 = km_1$ (a special attention need to be paid when one of the $m_1$, $n_1$ is zero) On one hand, $m_2n_3 - m_3n_2 = k (m_1n_3 - m_3n_1)$, implies that $k = \pm 1$. On the other hand $(m_2n_4 - m_4n_2) - (m_3n_4 - m_4n_3) = 0, \pm 2$ and $(m_2n_4 - m_4n_2) - (m_3n_4 - m_4n_3) = k(m_1n_4 -m_4n_1)$, implies that $k =0, \pm 2$. Contradiction.
10.03.2021 11:19
A different solution using geometry and combinatorics: Lemma: If we have two points $P_1=(m_1,n_1)$ nd $P_2(m_2,n_2)$ then if a third point must exist should be either of but not all of $(m_2-m_1,n_2-n_1)$ , $(m_1-m_2,n_1-n_2)$ , $(m_1+m_2,n_1+n_2)$and call this point the "Good Point" Notation: Call the good point corresponding to $P_i,P_j$ to be $G_{i,j}$ Proof: Simple via proving that the quadrilateral $OP_1P_2P_3$ must be a parallelogram. Lemma: Given 4 lattice points say $P_1,P_2,P_3,P_4$ the Good Points generated by 6 of the triangles must be unique Proof: Let us suppose for sake of the contradiction that the contrary is what holds true Now the good point $G_{1,2}$ is the same for two such triangles say for $OP_1P_2$ and $OP_3P_4$ then $[OP_1P_2G_1] = [ OP_3P_4G_1] $ Now we also have $[OP_2G_1]=\frac{1}{2}$ and since $OG_1 \parallel P_1P_2 \parallel P_3P_4 $ This gives $P_1,P_2,P_3,P_4 $is collinear from which arises a contradiction. Now the largest set S must have the property that $ P_i, P_j \in S \implies G_{i,j} \in S $ . Therefore $\binom{r}{2}= r \implies r=3$ Q.E.D
15.03.2021 11:59
Let $\vec v_1=\begin{pmatrix}m_1\\n_1\end{pmatrix}, \vec v_2=\begin{pmatrix}m_2\\n_2\end{pmatrix}, \cdots ,\vec v_r=\begin{pmatrix}m_r\\n_r\end{pmatrix}$. We have $|\det(\vec v_i,\vec v_j)|=1$ for $i\neq j$. We show $r=4$ isn't possible. As $\begin{pmatrix}1\\0\end{pmatrix}, \begin{pmatrix}0\\1\end{pmatrix}$ and $\begin{pmatrix}1\\1\end{pmatrix}$ satisfy the hypothesis, this would imply that $r=3$ is the required maximum. As $\det(\vec v_1,\vec v_2)=1\neq0$, $\vec v_1$ and $\vec v_2$ form a basis of $\mathbb{R}^2$. Suppose $\vec v_3$ and $\vec v_4$ have coordinates $\begin{pmatrix}\lambda_1\\ \lambda_2\end{pmatrix}$ and $\begin{pmatrix}\mu_1\\ \mu_2\end{pmatrix}$ in the basis $\vec v_1,\vec v_2$, that is, $$\vec v_3=A\begin{pmatrix}\lambda_1\\ \lambda_2\end{pmatrix}\text{and }\vec v_4=A\begin{pmatrix}\mu_1\\ \mu_2\end{pmatrix}\text{, where }A=[\vec v_1,\vec v_2].$$ In this setup, $\det(\vec v_1,\vec v_3)=\det\bigg(A\begin{pmatrix}1 & \lambda_1\\ 0 & \lambda_2\end{pmatrix}\bigg)=\det(A)\lambda_2$. Therefore, $|\lambda_2|=1$. Similarly, $|\lambda_1|=|\lambda_2|=|\mu_1|=|\mu_2|=1$. However, $\det(\vec v_3,\vec v_4)=\det\bigg(A\begin{pmatrix}\lambda_1 & \mu_1\\ \lambda_2 & \mu_2 \end{pmatrix}\bigg)=\begin{vmatrix}\lambda_1 & \mu_1\\ \lambda_2 & \mu_2 \end{vmatrix}$ which can only take the values $0, 2, $ and $-2$, a contradiction. P.S.- Note we didn't use the hypothesis that $m_i, n_i$ are integers.
20.03.2021 22:48
anantmudgal09 wrote: Suppose $r \ge 2$ is an integer, and let $m_1, n_1, m_2, n_2, \dots, m_r, n_r$ be $2r$ integers such that $$\left|m_in_j-m_jn_i\right|=1$$for any two integers $i$ and $j$ satisfying $1 \le i<j \le r$. Determine the maximum possible value of $r$. Proposed by B Sury Clearly as we need $\left|m_in_j-m_jn_i\right|=1$ So both $m_i, n_i$ Can never Simultaneously be even. Now let's start with $m_1,n_1$ Case 1-: if both $m_1, n_1$ is odd for then we must have one of $m_2, n_2$ even, Say if $m_2$ is even, then $n_2$ is odd Then clearly by above relation we need all $m_j$ odd for all $r\geq j>1$ and then $n_j$ is even for all $r\geq j>1$ Now if $r\geq 4$ then $n_4,m_4$ will be even and odd respectively but we also have $|m_3n_4-m_4n_3|=1$ which is never possible. Hence contradiction $r\leq 3$ in this case. Case 2-: If $m_1, n_1$ are of different parity say $m_1$ is even and $n_1$ is odd. Then $\left|m_1n_j-m_jn_1\right|=1$ so $m_j$ is odd for all $r\geq j>1$ Now if $n_2$ is even then $n_j$ is odd for all $r\geq j>1$ then if $r\geq 4$ But then $\left|m_3n_4-m_4n_3\right|=1$ can never be odd, Contradiction . Similarly we can achieve contradiction when $n_2$ is odd. Hence Max value of $r$ is $3$ in this case also. So overall maximum value of $r$ is $3$ $\blacksquare$
16.01.2022 11:09
If $m_i,n_i$ are all odd, $m_in_j-m_jn_i$ is even. So WLOG we assume $m_1$ is even. $|m_1n_j-m_jn_1|=1$ $\implies m_jn_1$ is odd. Hence $m_j$ is odd for all $j \neq 1$. We pick $t,x \neq 1$ $|m_tn_x-m_xn_t|=1 \implies n_x - n_t \equiv 1(\mod 2)$.....(1) If $r\geq 4$, $n_4-n_3$ is odd from (1). $n_4-n_2$ is odd again. $n_3-n_2$ is odd. But $(n_4-n_2)=(n_4-n_3)+(n_3-n_2)=(\text{odd})+(\text{odd})=(\text{even})$, which is a clear contradiction. So $r\le 3$. Construction for $r=3$, $(m_1,m_2,m_3) = (2,3,1)$ and $(n_1,n_2,n_3) = (1,2,1)$
18.01.2025 10:57