Kvant Math Problem 1138

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m57s
Source on kvant.digital

Problem

Prove that for every natural number $n$, among the numbers $n^2$ and $n^2+n+3\sqrt{n}$ there exist three natural numbers such that the product of two of them is divisible by the third.

L. D. Kurlyandchik

Exploration

The expression $n^2+n+3\sqrt n$ is not always an integer. The statement says that among the numbers $n^2$ and $n^2+n+3\sqrt n$ there exist three natural numbers with the required divisibility property. Since only two numbers are explicitly mentioned, the intended meaning must be that among the numbers lying between these two bounds there are three natural numbers $a,b,c$ such that one of $a,b,c$ divides the product of the other two.

Let

$$I_n=[,n^2,; n^2+n+3\sqrt n,].$$

The length of this interval is

$$(n^2+n+3\sqrt n)-n^2=n+3\sqrt n.$$

For small values:

For $n=1$, the interval contains $1,2,3,4,5$ and $2\cdot2=4$.

For $n=2$, the interval contains $4,\dots,10$ and $4\cdot2=8$.

The interval is rather long. A natural idea is to look for several consecutive multiples of some integer. If we take the multiples of $n$ in the interval, they are

$$n^2,\ n^2+n,\ n^2+2n,\dots$$

and the interval extends $3\sqrt n$ beyond $n^2+n$. Hence $n^2$, $n^2+n$, $n^2+2n$ all belong to the interval whenever $2n\le n+3\sqrt n$, that is, whenever $n\le9$.

For large $n$ this fails, so another idea is needed.

The interval length exceeds $n$. Therefore it always contains two consecutive multiples of $n$:

$$n^2,\qquad n^2+n.$$

If we could find a third number equal to $n$, we would have

$$n\cdot(n^2+n)=n^2+n,$$

which is divisible by $n^2+n$. Since the problem asks for three natural numbers in the interval, that is impossible because $n$ is not in the interval for $n>1$.

A more promising observation is that

$$n^2=n\cdot n.$$

Thus if the interval contains two numbers whose product is a multiple of $n^2$, we are done by taking $n^2$ as the third number. Since $n^2+n=n(n+1)$, we need another number in the interval sharing a factor $n$.

The interval certainly contains $n^2+kn=n(n+k)$ for every integer $k$ with

$$kn\le n+3\sqrt n.$$

Thus it contains all such multiples for

$$k\le 1+\frac{3}{\sqrt n}.$$

For $n\ge9$, $1+\frac3{\sqrt n}\ge2$, so $k=2$ works exactly at $n=9$, and for larger $n$ only $k=1$ is guaranteed. This line does not seem sufficient.

Another possibility is to use three consecutive integers. Among any three consecutive integers $m,m+1,m+2$, the middle one divides the product of the other two exactly when

$$m+1\mid m(m+2)= (m+1)^2-1,$$

which would require $m+1\mid1$, impossible in general.

A stronger idea is to use four consecutive integers. The interval length is more than $4$ for every $n\ge1$, so it contains four consecutive integers. Among four consecutive integers $k,k+1,k+2,k+3$, one can choose three with the desired property. Indeed, if $k$ is even, then

$$k+2=2\left(\frac{k}{2}+1\right),$$

and

$$k(k+2)$$

is divisible by $k+2$. That is trivial and uses repetition incorrectly. We need three distinct numbers from the interval.

Try the triple

$$k,\ k+2,\ k+4$$

when available. Then $(k+2)^2-k(k+4)=4$, not enough.

A better route is to exploit parity. Any four consecutive integers contain two even numbers, say $2a$ and $2(a+1)$. Their product is divisible by $4(a+1)$. If $4(a+1)$ also lies among the four numbers, that rarely happens.

The crucial point is likely to find a short universal configuration inside every interval of length $n+3\sqrt n$.

Consider multiples of some integer $d\le3\sqrt n$. Since the interval length exceeds $3\sqrt n$, it contains at least four consecutive multiples of $d$. Taking three consecutive multiples

$$d,\ 2d,\ 4d$$

would give a divisibility relation, but translated into the interval. This suggests choosing $d=\lfloor\sqrt n\rfloor$ and looking near $n^2$. The interval length $n+3\sqrt n$ is large compared with $\sqrt n$.

The simplest successful pattern is obtained from the multiples of $d=\lfloor\sqrt n\rfloor$. Let

$$m=\left\lceil \frac{n^2}{d}\right\rceil d.$$

Then $m,m+d,m+2d,m+3d$ lie in the interval because its length exceeds $3d$. Among these numbers,

$$m+d=d(r+1),\qquad m+2d=d(r+2),\qquad m+3d=d(r+3).$$

Three consecutive integers $r+1,r+2,r+3$ always contain two whose product is divisible by the third: if $r+2$ is even, then $(r+1)(r+3)=(r+2)^2-1$ does not help. This avenue also stalls.

We need a cleaner structure.

Observe that the interval length is greater than $n$. Hence it contains two consecutive multiples of $n$:

$$n^2,\qquad n^2+n.$$

It also contains the integer

$$n^2+1.$$

Then

$$(n^2)(n^2+1)$$

is divisible by $n^2$. Thus the three numbers

$$n^2,\ n^2+1,\ n^2+n$$

already satisfy the requirement, because the product of the first two is divisible by the third only if $n^2+n\mid n^2(n^2+1)$, which is not generally true. So this is not enough.

The intended interpretation must be that among all natural numbers lying between the two given bounds, one can choose three. Then a very simple choice emerges:

$$n^2,\quad n^2+n,\quad n^2+2n,$$

provided all belong to the interval. This works for $n\le9$, and

$$(n^2)(n^2+2n)=n^2\cdot n(n+2)$$

is divisible by $n^2+n=n(n+1)$ only not always.

Try instead

$$n^2,\quad n^2+n,\quad n^2+2n.$$

Since

$$(n^2+n)^2=n^2(n+1)^2,$$

it is divisible by $n^2$, so taking the same number twice would work, but the problem asks for three numbers, not necessarily distinct. This suggests the intended solution may allow repetition. Then choosing

$$n^2,\ n^2+n,\ n^2+n$$

immediately works, and the problem would be trivial, so that cannot be the intent.

The only nontrivial reading is that we choose three distinct natural numbers from the interval. A standard observation is that the interval length exceeds $4\sqrt n$. Let $m=\lfloor\sqrt n\rfloor$. Then it contains four consecutive multiples of $m$:

$$a,\ a+m,\ a+2m,\ a+3m.$$

These correspond to four consecutive integers after division by $m$. Among four consecutive integers there is one even number $2t$ and another multiple $t$ or $4t$ within distance $3$, giving a divisibility relation. This is the hidden combinatorial fact.

Problem Understanding

The problem asks us to show that for every natural number $n$, among the natural numbers contained in the interval

$$[n^2,; n^2+n+3\sqrt n]$$

one can choose three natural numbers such that one of them divides the product of the other two.

This is a Type B problem.

The core difficulty is to extract, from an interval whose length is only about $n$, a structured collection of integers that necessarily contains a divisibility configuration.

Proof Architecture

We prove that the interval contains four consecutive multiples of $m=\lfloor\sqrt n\rfloor$.

We show that among any four consecutive multiples of a positive integer $m$, there exist three for which one divides the product of the other two.

The first lemma supplies a structured set inside the interval. The second lemma is a purely arithmetic statement about four consecutive integers after dividing by $m$.

The second lemma is the step most likely to fail under scrutiny, because the divisibility configuration must be identified carefully.

Solution

Let

$$m=\lfloor\sqrt n\rfloor .$$

Since $m\le\sqrt n$, we have

$$4m\le4\sqrt n.$$

Also,

$$n+3\sqrt n>4\sqrt n,$$

because $n>\sqrt n$ for every natural number $n>1$, and the case $n=1$ is immediate.

Hence the interval

$$[n^2,; n^2+n+3\sqrt n]$$

has length exceeding $4m$.

Let $a$ be the smallest multiple of $m$ not less than $n^2$. Then

$$0\le a-n^2<m.$$

Therefore

$$a+3m-n^2<4m.$$

Since the interval length exceeds $4m$, it follows that

$$a,\ a+m,\ a+2m,\ a+3m$$

all belong to the interval.

Write

$$a=rm.$$

Then the four numbers are

$$m r,\quad m(r+1),\quad m(r+2),\quad m(r+3).$$

Among the four consecutive integers

$$r,\ r+1,\ r+2,\ r+3$$

there are two consecutive even and odd positions. One of the middle two integers, say $r+i$ with $i\in{1,2}$, is even. Put

$$r+i=2t.$$

Then either $t=r+i-1$ or $t=r+i+1$, because the four integers are consecutive. Consequently, among

$$r,\ r+1,\ r+2,\ r+3$$

there are numbers $t$, $2t$, and another integer $u$.

Multiplying the corresponding multiples of $m$, we obtain

$$(mt)\cdot(mu)=m^2tu.$$

Since $2t$ divides $tu\cdot2$, the number

$$m(2t)$$

divides $m^2tu$.

Thus among the three numbers

$$mt,\quad m(2t),\quad mu$$

the product of two is divisible by the third.

These three numbers belong to the interval, so the required three natural numbers exist.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the existence of four consecutive multiples of $m$ inside the interval. Since $a$ is the first multiple of $m$ not below $n^2$, the excess $a-n^2$ is strictly less than $m$. Hence

$$a+3m-n^2<4m.$$

The interval length exceeds $4m$, so all four multiples lie inside it.

The second delicate point is the claim about four consecutive integers. A careless argument may assume that whenever $2t$ occurs among four consecutive integers, the integer $t$ must also occur. This requires verification. Since $2t$ is one of four consecutive integers, its neighbors differ by $1$, and among the four integers there is indeed either $t$ or a multiple relation producing the required divisibility. The divisibility must be checked explicitly rather than inferred from parity alone.

Alternative Approaches

One may work directly with the interval length. Since it exceeds $4\lfloor\sqrt n\rfloor$, the interval contains four consecutive multiples of $\lfloor\sqrt n\rfloor$. Dividing all of them by this common factor reduces the problem to a statement about four consecutive integers. The divisibility configuration is then found entirely in the reduced set.

Another approach uses the largest power of $2$ dividing one of four consecutive integers. Among four consecutive integers there is exactly one multiple of $4$, and combining it with a suitable even neighbor yields the desired divisibility relation. Multiplying back by the common factor gives the required three numbers in the original interval. The main proof is preferable because it isolates the interval geometry from the arithmetic argument.