Maths Olympiad Prep

Library / /73 of 121

Number theory Difficulty 6.3 National Olympiad Prove it India

Problem:
Suppose r2r \geq 2 is an integer, and let m1,n1,m2,n2,,mr,nrm_{1}, n_{1}, m_{2}, n_{2}, \cdots, m_{r}, n_{r} be 2r2 r integers such that
minjmjni=1 \left|m_{i} n_{j}-m_{j} n_{i}\right|=1
for any two integers ii and jj satisfying 1i<jr1 \leq i<j \leq r. Determine the maximum possible value of rr.

Solution

Solution:
Let m1,n1,m2,n2m_{1}, n_{1}, m_{2}, n_{2} be integers satisfying m1n2m2n1=±1m_{1} n_{2}-m_{2} n_{1}= \pm 1. By changing the signs of m2,n2m_{2}, n_{2} if need be, we may assume that
m1n2m2n1=1 m_{1} n_{2}-m_{2} n_{1}=1
If m3,n3m_{3}, n_{3} are integers satisfying m1n3m3n1=±1m_{1} n_{3}-m_{3} n_{1}= \pm 1, again we may assume (by changing their signs if necessary) that
m1n3m3n1=1 m_{1} n_{3}-m_{3} n_{1}=1
So m1(n2n3)=n1(m2m3)m_{1}\left(n_{2}-n_{3}\right)=n_{1}\left(m_{2}-m_{3}\right).
As m1,n1m_{1}, n_{1} are relatively prime, m1m_{1} divides m2m3m_{2}-m_{3}; say, m2m3=m1am_{2}-m_{3}=m_{1} a for some integer aa. Thus, we get n2n3=n1an_{2}-n_{3}=n_{1} a. In other words,
m3=m2m1a,n3=n2n1a m_{3}=m_{2}-m_{1} a, \quad n_{3}=n_{2}-n_{1} a
Now, if m2n3n2m3=±1m_{2} n_{3}-n_{2} m_{3}= \pm 1, we get
±1=m2(n2n1a)n2(m2m1a)=(m1n2m2n1)a=a \pm 1=m_{2}\left(n_{2}-n_{1} a\right)-n_{2}\left(m_{2}-m_{1} a\right)=\left(m_{1} n_{2}-m_{2} n_{1}\right) a=a
Thus, m3=m2m1a=m2±m1,n3=n2n1a=n2±n1m_{3}=m_{2}-m_{1} a=m_{2} \pm m_{1}, \quad n_{3}=n_{2}-n_{1} a=n_{2} \pm n_{1}.
Now if we were to have another pair of integers m4,n4m_{4}, n_{4} such that
m1n4n1m4=±1 m_{1} n_{4}-n_{1} m_{4}= \pm 1
we may assume that m1n4n1m4=1m_{1} n_{4}-n_{1} m_{4}=1. As seen above, m4=m2m1,n4=n2n1m_{4}=m_{2} \mp m_{1}, \quad n_{4}=n_{2} \mp n_{1}. But then
m3n4n3m4=(m2±m1)(n2n1)(n2±n1)(m2m1)=±2 m_{3} n_{4}-n_{3} m_{4}=\left(m_{2} \pm m_{1}\right)\left(n_{2} \mp n_{1}\right)-\left(n_{2} \pm n_{1}\right)\left(m_{2} \mp m_{1}\right)= \pm 2
Therefore, there can be only 3 pairs of such integers.

Alternate Solution:
It is clear that rr can be 3 due to the valid solution m1=1,n1=1,m2=1,n2=2,m3=2,n3=3m_{1}=1, n_{1}=1, m_{2}=1, n_{2}=2, m_{3}=2, n_{3}=3.
If possible, let r>3r>3. We observe that:
m1n2n3m2n1n3=±n3m2n3n1m3n2n1=±n1m3n1n2m1n3n2=±n2 \begin{aligned} & m_{1} n_{2} n_{3}-m_{2} n_{1} n_{3}= \pm n_{3} \\ & m_{2} n_{3} n_{1}-m_{3} n_{2} n_{1}= \pm n_{1} \\ & m_{3} n_{1} n_{2}-m_{1} n_{3} n_{2}= \pm n_{2} \end{aligned}
Adding, we get ±n1±n2±n3=0\pm n_{1} \pm n_{2} \pm n_{3}=0; which forces at least one of n1,n2,n3n_{1}, n_{2}, n_{3} to be even; WLOG let n1n_{1} be even.
Repeating the argument for indices 2,3,42,3,4, we deduce that at least one of n2,n3,n4n_{2}, n_{3}, n_{4} is even; WLOG let n2n_{2} be even. This leads to a contradiction, since m1n2m2n1=1\left|m_{1} n_{2}-m_{2} n_{1}\right|=1 cannot be even. Hence r>3r>3 is not possible, as claimed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.