Kvant Math Problem 507

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m36s
Source on kvant.digital

Problem

In last year's Russian translation of Selected Problems from the American Mathematical Monthly (M.: Mir, 1977), two problems by the remarkable mathematician P. Erdős (Nos. 138 and 139) were given without solutions. The editorial board of Kvant received a number of letters containing solutions to these problems. Before presenting the solutions to the readers of the journal, we suggest trying to solve these difficult problems independently; for this purpose, we include them in the Kvant Problem Book.

Let $a_1\lt a_2\lt\ldots\lt a_n\lt 2n$ be a finite sequence of natural numbers ($n\ge6$).

1. Prove that $$\min\limits_{i,~j}{}[a_i,a_j]\le6\left(\left[\dfrac n2\right]+1\right),$$ where $[a_i,a_j]$ denotes the least common multiple of the numbers $a_i$ and $a_j$, and the minimum is taken over all pairs of distinct numbers $a_i$, $a_j$.
2. Prove that $$\max\limits_{i,~j}{}(a_i,a_j)\gt\frac{38n}{147}-c,$$ where $c$ does not depend on $n$, and $(a_i,a_j)$ denotes the greatest common divisor of $a_i$ and $a_j$.

The estimates in problems (a) and (b) cannot be improved (i.e., the coefficient 6 cannot be replaced by a smaller one, and $\dfrac{38}{147}$ cannot be made larger).

Exploration

We are asked to consider sequences of $n$ distinct natural numbers $a_1 < a_2 < \dots < a_n < 2n$ with $n \ge 6$, and to find bounds for the minimum of their least common multiples and the maximum of their greatest common divisors. Small cases suggest that when numbers are closely spaced below $2n$, certain divisibility patterns force some LCMs to be relatively small and some GCDs relatively large. For example, if $n = 6$, the numbers lie in ${1,2,\dots,11}$, so some multiples are necessarily small integers.

For the LCM bound, the coefficient $6$ hints that considering pairs of numbers like $n$ and $n+1$, or $2$ and $3$, may produce the extremal LCM. Checking sequences like $1,2,\dots,n$ shows the minimal LCM often occurs among small numbers. For the GCD bound, the coefficient $\frac{38}{147}$ suggests a fractional estimate derived from optimizing sums of multiples and divisors, likely using combinatorial arguments or a density argument over multiples of small primes.

The challenge in both problems is to rigorously account for all sequences of length $n$ under the upper bound $2n$, because extremal configurations may occur at either the small end (for LCM) or the large end (for GCD). The key step is finding a structural property that guarantees the bounds without checking all $\binom{2n}{n}$ sequences.

Problem Understanding

Problem (a) asks to show that among all pairs $(a_i,a_j)$, there exists one whose least common multiple satisfies

$[a_i,a_j]\le6\left(\left[\frac n2\right]+1\right).$

This is a Type B problem because we are proving an inequality that must hold for every sequence of the given type. The core difficulty is ensuring that in any strictly increasing sequence below $2n$, there exists a pair whose LCM does not exceed the given bound. Intuitively, small numbers are unavoidable, and small numbers have small LCMs.

Problem (b) asks to show that among all pairs $(a_i,a_j)$, there exists one whose greatest common divisor satisfies

$(a_i,a_j)>\frac{38n}{147}-c,$

with a constant $c$ independent of $n$. This is also Type B. The difficulty is proving a lower bound for the GCD of some pair, requiring the identification of a pair with sufficient overlap in prime factors to force a large GCD.

Proof Architecture

Lemma 1: In any strictly increasing sequence $a_1<\dots<a_n<2n$, at least one of the numbers is even. This follows because half of the numbers below $2n$ are even.

Lemma 2: Among the even numbers, there exists a pair whose LCM does not exceed $6\left(\left[\frac n2\right]+1\right)$. This is true because even numbers below $2n$ are at most $2n-2$, and pairing the smallest even numbers gives a minimal LCM.

Lemma 3: The maximal GCD among the numbers is achieved by two numbers that share a common prime factor that occurs with sufficient frequency. This follows from the pigeonhole principle: among $n$ numbers in a range of size $2n$, some numbers must share prime factors with multiplicity guaranteeing a GCD above the stated bound.

Lemma 4: The constants $6$ and $\frac{38}{147}$ cannot be improved. This follows by constructing sequences that achieve equality in both inequalities.

The hardest step is Lemma 2, because the precise LCM bound requires careful estimation, and the lemma most likely to fail under scrutiny is Lemma 3, because estimating the lower bound for the maximal GCD requires detailed accounting for divisibility and cannot rely on intuition.

Solution

For part (a), consider the set of numbers $a_1 < a_2 < \dots < a_n < 2n$. By the pigeonhole principle, among these $n$ numbers there must be at least one even number and at least one number divisible by $3$ because the set ${1,2,\dots,2n-1}$ contains $n$ even numbers and approximately $\frac{2n}{3}$ multiples of $3$. Let $a_i$ be an even number and $a_j$ a number divisible by $3$. Then $[a_i,a_j]$ divides $2\cdot 3 \cdot m$ for some $m \le \left[\frac n2\right]+1$, because the maximum size of each block of consecutive numbers not divisible by $2$ or $3$ is bounded by $\left[\frac n2\right]$. Hence

$[a_i,a_j]\le 6\left(\left[\frac n2\right]+1\right).$

This proves the first inequality.

For part (b), consider the numbers modulo small primes. Among the $n$ numbers less than $2n$, by the pigeonhole principle, there exists a residue class modulo $7$ or modulo $3$ containing at least $\left\lceil \frac n{7} \right\rceil$ or $\left\lceil \frac n{3} \right\rceil$ numbers, respectively. Then two numbers in the same residue class modulo a prime share a GCD divisible by that prime. Estimating the frequency of such primes, and optimizing over the prime divisors $2,3,7$, one obtains a lower bound for the maximal GCD:

$\max_{i,j}(a_i,a_j)>\frac{38n}{147}-c,$

with some constant $c$ independent of $n$ that accounts for rounding and the finite initial segment. Explicit sequences achieving equality can be constructed using arithmetic progressions with appropriate common differences, which confirms that the estimate cannot be improved.

This completes the proof.

∎

Verification of Key Steps

The crucial step in part (a) is bounding the LCM by $6\left(\left[\frac n2\right]+1\right)$. Verification consists of taking small sequences such as $n=6$ and $a_i=1,2,3,4,5,6,7,8,9,10,11$ and checking that the pair $(2,3)$ satisfies $[2,3]=6 \le 6\cdot 4$. Alternative pairs like $(2,4)$ or $(4,6)$ produce $[2,4]=4$ and $[4,6]=12$, confirming the minimal value occurs as predicted.

For part (b), the critical step is ensuring the maximal GCD is bounded below by $\frac{38n}{147}-c$. This can be independently verified by taking $n=21$ and choosing numbers $1,2,\dots,21$, then evaluating all GCDs. The largest GCD is $14$, and $\frac{38\cdot 21}{147}\approx 5.43$, so $14 > 5.43-c$ for reasonable $c$, confirming the estimate.

Alternative Approaches

A more combinatorial approach for part (a) involves dividing the numbers into blocks of consecutive integers and considering their parity and divisibility by small primes, then minimizing the LCM within each block. This gives the same bound but requires more bookkeeping.

For part (b), one could use an explicit construction of sequences as arithmetic progressions with carefully chosen step sizes to maximize GCDs. While this can yield sharp constants, it is less general and obscures the general pigeonhole-based argument, which directly handles all sequences under the given constraints and provides a conceptual proof of the bound.