Prove that for every positive integer $n$ there do not exist four positive integers $a,b,c,d$ with $ad = bc$ and $n^2 < a < b < c < d < (n+1)^2$.

140 Views Asked by At

Here is the problem Timothy Gowers was trying to solve in this YouTube video.

Prove that for every positive integer $n$ there do not exist four positive integers $a,b,c,d$ with $ad = bc$ and $n^2 < a < b < c < d < (n+1)^2$.

The problem seems to be related to the determinant of the $2 \times 2$ matrix $\begin{pmatrix}a&b\\ c&d\end{pmatrix}$. The condition $ad = bc$ is equivalent to $$\det \begin{pmatrix}a&b\\ c&d\end{pmatrix} = 0.$$

Geometrically this mean that the space spanned by the vectors $(a,b)$ and $(c,d)$ is a line. Is there a way to relate this to the given problem or is it just a coincidence?

1

There are 1 best solutions below

0
On

All variables are positive integers.

It is enough to prove the following claim.

Claim: Suppose $n^2\le a<b\le c<d\le (n+1)^2$ and $ad=bc$. Then $a=n^2$, $b=c=n(n+1)$, $d=(n+1)^2$.

Proof: $ad=bc\implies\frac dc=\frac ba.$ Hence $$d-c=c(\frac dc-1)> a(\frac ba-1)=b-a.$$

Let $k=b-a$. Since $d-c$ and $b-a$ are integers, $d-c\ge k+1$. (This "$+\ 1$" is critical.)

$$\begin{aligned}&\quad\ \,ad-bc\\&=ad-(a+k)(d-(d-c))\\ &\ge ad-(a+k)(d-(k+1))\\ &=(k+1)a-kd+k(k+1)\\ &\ge (k+1)n^2-k(n+1)^2+k^2+k\\ &=(n-k)^2\\ &\ge0 \end{aligned}$$ Since $ad=bc$, all inequalities above must be equalities, i.e., $d-c=k+1$, $a=n^2$, $d=(n+1)^2$, and $k=n$. Hence $b=a+k=n(n+1)$ and $c=d-(k+1)=n(n+1)$.