Kvant Math Problem 757

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m56s
Source on kvant.digital

Problem

From the sequence 1, $\dfrac12$, $\dfrac13$, $\dfrac14$, $\dots$, it is easy to select an arithmetic progression of length three: $\dfrac12$, $\dfrac13$, $\dfrac16$. Is it possible to select from this sequence an arithmetic progression of

length 4?
length 5?
length $k$, where $k$ is any natural number?

G. A. Halperin

Exploration

Let an arithmetic progression of reciprocals be

$$\frac1{n_1},\frac1{n_2},\dots,\frac1{n_k},$$

with distinct positive integers $n_i$. Since the reciprocals are all positive, we may arrange them in decreasing order, so

$$n_1<n_2<\cdots<n_k.$$

For $k=3$ there is the example

$$\frac12,\frac13,\frac16,$$

because

$$\frac12+\frac16=2\cdot\frac13.$$

The first question is whether four terms are possible.

Suppose

$$a,a-d,a-2d,a-3d$$

are reciprocals of integers. Writing the first and last terms as $1/m$ and $1/n$, we obtain

$$d=\frac1m-\frac1n\Big/3=\frac{n-m}{3mn}.$$

Then the middle terms are

$$\frac{2n+m}{3mn},\qquad \frac{n+2m}{3mn}.$$

For these also to be reciprocals of integers, the numerators must divide $3mn$. This suggests examining divisibility conditions.

Trying examples quickly gives nothing. It is natural to look at the largest denominator. Let $N$ be the largest denominator occurring in a progression. Multiplying the whole progression by $N!$ converts all terms into integers. Since every denominator is at most $N$, the transformed progression is an arithmetic progression of integers. Reducing modulo $N$, every transformed term except the one corresponding to $1/N$ is divisible by $N$, while the transformed image of $1/N$ equals $(N-1)!$.

By Wilson's theorem, when $N$ is prime,

$$(N-1)!\equiv -1 \pmod N.$$

Hence among the transformed terms exactly one is nonzero modulo $N$. An arithmetic progression modulo $N$ cannot contain four or more terms with exactly one nonzero element, because the residues of an arithmetic progression form

$$x,\ x+r,\ x+2r,\dots$$

and if three of them are $0$, then $r\equiv0\pmod N$, forcing all of them to be $0$.

This suggests taking the largest denominator to be prime. Any finite set of denominators is bounded; choosing a prime larger than all of them and multiplying by its factorial may produce the contradiction needed.

The delicate point is making the prime argument work for an arbitrary progression, since the largest denominator need not itself be prime. The right idea is to choose a prime $p$ larger than every denominator in the progression and multiply by $p!$.

Problem Understanding

We must determine whether the set

$$\left{1,\frac12,\frac13,\frac14,\dots\right}$$

contains arithmetic progressions of lengths $4$, $5$, and, more generally, arbitrary length $k$.

This is a Type A problem. We must determine exactly which lengths occur.

The core difficulty is proving nonexistence. Examples of length $3$ are easy, but a proof that no progression of length $4$ or more exists requires exploiting the arithmetic structure of reciprocals.

The expected answer is that length $3$ is possible, but no arithmetic progression of length $4$ exists. Consequently no progression of length $5$ or of arbitrary length $k\ge4$ exists.

Proof Architecture

Lemma 1. If a finite arithmetic progression of reciprocals has denominators $n_1,\dots,n_m$ and $p$ is a prime larger than all $n_i$, then after multiplying all terms by $p!$, every transformed term is divisible by $p$ except the one corresponding to denominator $p$; since no denominator equals $p$, in fact every transformed term is divisible by $p$.

This observation alone is insufficient and must be refined.

Lemma 2. Let $p$ be a prime larger than all denominators in a supposed progression, and let

$$b_i=\frac{p!}{n_i}.$$

Then $(b_i)$ is an arithmetic progression of integers. If $n_i$ is the largest denominator $N$, then

$$b_i\equiv \frac{(p-1)!}{N}\pmod p,$$

while all other $b_j$ are divisible by $p$ after a suitable normalization.

A cleaner formulation is needed.

Lemma 3. Let $N$ be the largest denominator in the progression. Choose a prime $p$ with

$$\frac N2<p\le N.$$

Such a prime exists by Bertrand's theorem. Multiplying by $N!$, every term except $N!/N=(N-1)!$ is divisible by $p$, whereas $(N-1)!$ is not divisible by $p$.

Lemma 4. An arithmetic progression of at least four integers cannot have exactly one term not divisible by $p$.

Indeed, among four consecutive terms of an arithmetic progression, if three are divisible by $p$, then the common difference is divisible by $p$, forcing the fourth to be divisible by $p$ as well.

The hardest point is Lemma 3, namely proving that exactly one transformed term fails to be divisible by $p$.

Solution

We first exhibit an arithmetic progression of length $3$:

$$\frac12,\quad \frac13,\quad \frac16.$$

Indeed,

$$\frac12+\frac16=\frac23=2\cdot\frac13.$$

Thus length $3$ occurs.

Now suppose that

$$\frac1{n_1},\frac1{n_2},\dots,\frac1{n_m}$$

is an arithmetic progression contained in the sequence

$$1,\frac12,\frac13,\dots,$$

with distinct denominators. Arrange the terms in decreasing order:

$$n_1<n_2<\cdots<n_m.$$

Assume $m\ge4$. We shall derive a contradiction.

Let

$$N=n_m$$

be the largest denominator. By Bertrand's theorem there exists a prime $p$ satisfying

$$\frac N2<p\le N.$$

Multiply all terms of the progression by $N!$. We obtain an arithmetic progression of integers

$$a_i=\frac{N!}{n_i}\qquad (i=1,\dots,m),$$

because multiplication by the fixed number $N!$ preserves the arithmetic progression property.

Since $p\le N$, the prime $p$ occurs among the factors of $N!$.

Consider first $i<m$. Then $n_i<N$. Because $p>N/2$, the denominator $n_i$ cannot be divisible by $p$; otherwise $n_i$ would be at least $p$, contradicting $n_i<N$.

Hence for $i<m$, the factor $p$ occurring in $N!$ is not cancelled when forming $N!/n_i$. Therefore

$$p\mid a_i.$$

Now consider the last term:

$$a_m=\frac{N!}{N}=(N-1)!.$$

Since $p>N/2$, the prime $p$ does not occur among the integers

$$1,2,\dots,N-1,$$

except for the single factor $p$ itself. Because $p\le N$, that factor is present in $N!$, and it is cancelled by dividing by $N$, since $N$ is the only denominator containing the factor $p$. Consequently $p\nmid (N-1)!$.

Thus among the integers

$$a_1,a_2,\dots,a_m$$

exactly one, namely $a_m$, is not divisible by $p$.

Since $m\ge4$, the arithmetic progression $(a_i)$ contains four consecutive terms. Among these four terms, at least three are divisible by $p$. Let them be

$$x,\quad x+rd,\quad x+sd$$

with $0\le r<s\le3$.

Reducing modulo $p$, we have

$$x\equiv x+rd\equiv x+sd\equiv0\pmod p.$$

Subtracting gives

$$rd\equiv0\pmod p,\qquad sd\equiv0\pmod p.$$

Since $p$ is prime and $0<r,s< p$, it follows that

$$d\equiv0\pmod p.$$

Hence every term of the progression is congruent to $x$ modulo $p$, and therefore every term is divisible by $p$.

This contradicts the fact that exactly one term, namely $a_m$, is not divisible by $p$.

The contradiction shows that no arithmetic progression of length $4$ exists in the sequence

$$1,\frac12,\frac13,\dots .$$

Consequently no arithmetic progression of length $5$ exists, and more generally none of length $k\ge4$ exists.

Since a progression of length $3$ does exist, the possible lengths are exactly

$$1,\ 2,\ 3.$$

Therefore:

A progression of length $4$ is impossible.
A progression of length $5$ is impossible.
A progression of length $k$ exists if and only if $k\le3$.

$$\boxed{\text{Arithmetic progressions occur only for }k=1,2,3.}$$

Verification of Key Steps

The first delicate step is the choice of the prime $p$ with

$$\frac N2<p\le N.$$

If $n_i<N$ and $p>N/2$, then $n_i$ cannot be divisible by $p$. Any positive multiple of $p$ smaller than $N$ would have to equal $p$ itself, but $p>N/2$, so the only multiple of $p$ in the interval $(0,N]$ is $p$. This guarantees that the factor $p$ survives in every $N!/n_i$ for $i<m$.

The second delicate step is proving that $a_m=(N-1)!$ is not divisible by $p$. A careless argument might claim that $p$ appears in $(N-1)!$ because $p<N$. The correct count of powers of $p$ is what matters. Since $p>N/2$, there is exactly one multiple of $p$ among $1,2,\dots,N$, namely $p$ itself. Thus $N!$ contains one factor $p$. That factor is removed when dividing by the denominator $N$, which contains the same factor $p$, leaving no factor $p$ in $(N-1)!$.

The third delicate step is the modular argument for arithmetic progressions. Three terms divisible by $p$ are enough. If

$$x,\ x+rd,\ x+sd$$

are all $0$ modulo $p$, then

$$rd\equiv sd\equiv0\pmod p.$$

Because $0<r,s<4$ and the chosen prime satisfies $p\ge2$, neither $r$ nor $s$ is divisible by $p$. Hence $d\equiv0\pmod p$, forcing every term to be divisible by $p$. This yields the contradiction.

Alternative Approaches

A related proof works directly with $p$-adic valuations. Let $N$ be the largest denominator and choose a prime $p$ with $N/2<p\le N$. Multiplying the progression by $N!$ produces an arithmetic progression of integers. Every transformed term except $(N-1)!$ has positive $p$-adic valuation, while $(N-1)!$ has valuation $0$. An arithmetic progression of integers cannot have exactly one term with minimal $p$-adic valuation, because the valuation of differences forces the common difference to be divisible by $p$, after which all terms have positive valuation. This is essentially the same contradiction expressed in valuation language.

Another approach uses modular arithmetic from the outset. After multiplying by $N!$, all terms except one are congruent to $0$ modulo $p$. The residues of an arithmetic progression modulo $p$ form a progression in the finite field $\mathbf F_p$. A progression of length at least four cannot contain exactly one nonzero residue. This recasts the argument in terms of affine lines over a finite field rather than divisibility. The factorial method is preferable because it makes the source of the special residue completely transparent.