Kvant Math Problem 1352

Consider the definition of "close" numbers.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m49s
Source on kvant.digital

Problem

$n$ numbers ($n\gt1$) are called close if each of them is less than the sum of these numbers divided by $n-1$. Let $a$, $b$, $c$, $\ldots$ be $n$ close numbers, and let $S$ be their sum. Prove that

  1. all of them are positive;
  2. always $a+b\gt c$;
  3. always $a+b\ge\dfrac S{n-1}$.

R. Shleyfer

City Tournament

Exploration

Consider the definition of "close" numbers. For $n$ numbers $a_1, a_2, \dots, a_n$, each satisfies

$a_i < \frac{a_1 + a_2 + \dots + a_n}{n-1} = \frac{S}{n-1}.$

For $n = 2$, the inequality reduces to $a < b/(2-1) = b$ and $b < a$, which is impossible. Thus, the case $n = 2$ is excluded. For $n = 3$, let the numbers be $a, b, c$. The inequalities become $a < \frac{b+c}{2}$, $b < \frac{a+c}{2}$, $c < \frac{a+b}{2}$. Small numerical examples suggest that all numbers are positive and satisfy $a+b > c$. For instance, with $a=1, b=2, c=2$, we compute $S = 5$, then $S/(n-1) = 5/2 = 2.5$, and indeed $1<2.5$, $2<2.5$, $2<2.5$. Furthermore, $a+b = 3 > c = 2$, $a+b = 3 > S/(n-1) = 2.5$. This confirms the pattern. The main challenge is to rigorously prove positivity and the inequalities for arbitrary $n$, particularly ensuring the inequality $a+b \ge S/(n-1)$ holds for any pair of numbers.

The step most likely to hide an error is proving positivity, since the inequalities are strict but only relative to sums of $n-1$ numbers.

Problem Understanding

We are asked to prove three statements about $n>1$ numbers $a_1, \dots, a_n$ called "close", defined by the inequality $a_i < S/(n-1)$ for each $i$, where $S = a_1+\dots+a_n$. The problem is of Type B, a pure proof, because the statements to prove are explicitly given. The core difficulty is handling the dependence of each $a_i$ on the sum of all the numbers and ensuring strict inequalities lead to positivity and the sum inequalities.

Proof Architecture

Lemma 1: Every close number is positive. Sketch: Suppose one number is non-positive; summing the inequalities leads to a contradiction.

Lemma 2: For any three numbers $a, b, c$ among the $n$ numbers, $a+b>c$. Sketch: Apply the definition of closeness to $c$ and rearrange.

Lemma 3: For any two numbers $a, b$, $a+b \ge S/(n-1)$. Sketch: Sum inequalities for all other numbers except $a$ and $b$ to bound $S$ in terms of $a+b$.

The hardest direction is Lemma 1, since a naive assumption of negativity could superficially satisfy one inequality. Lemma 3 is most delicate because it involves $n$ variables and equality is non-obvious.

Solution

Let $a_1, a_2, \dots, a_n$ be close numbers and $S = a_1 + a_2 + \dots + a_n$.

Lemma 1. Every $a_i > 0$.

Suppose $a_1 \le 0$. Then the definition of closeness gives $a_1 < S/(n-1)$. If $a_1 \le 0$, then $S = a_1 + a_2 + \dots + a_n \le a_2 + \dots + a_n$. Thus

$\frac{S}{n-1} \le \frac{a_2 + \dots + a_n}{n-1}.$

On the other hand, for each $i = 2, \dots, n$, $a_i < S/(n-1) \le (a_2+\dots+a_n)/(n-1)$. Summing these $n-1$ inequalities yields

$a_2 + \dots + a_n < \frac{n-1}{n-1} (a_2 + \dots + a_n) = a_2 + \dots + a_n,$

which is impossible. Therefore $a_1 > 0$. By symmetry, all $a_i > 0$.

Lemma 2. For any $a, b, c$, $a+b>c$.

Consider $c$ as one of the numbers. By closeness, $c < S/(n-1)$. Then

$c < \frac{a+b + \sum_{\text{others}}}{n-1} = \frac{a+b + (S - a - b - c)}{n-1} = \frac{S - c}{n-1}.$

Multiplying both sides by $n-1$ gives $(n-1)c < S - c = (a+b) + \sum_{\text{others}}$. Subtracting the sum of the other numbers (all positive by Lemma 1) yields $a+b > c$.

Lemma 3. For any $a, b$, $a+b \ge S/(n-1)$.

Sum the inequalities for all numbers except $a$ and $b$:

$\sum_{i\ne a,b} a_i < \sum_{i\ne a,b} \frac{S}{n-1} = (n-2) \frac{S}{n-1}.$

The sum of all numbers except $a$ and $b$ is $S - a - b$. Thus $S - a - b < (n-2) S/(n-1)$. Rearranging gives $a+b > S - (n-2) S/(n-1) = S/(n-1)$.

Each lemma is proved; assembling them gives the required conclusions. This completes the proof.

∎

Verification of Key Steps

In Lemma 1, the critical step is summing $a_2 + \dots + a_n < (a_2 + \dots + a_n)$, which is impossible. Testing with small numbers like $a_1 = 0$, $a_2 = a_3 = 1$ confirms the contradiction arises precisely.

In Lemma 3, the rearrangement $S - a - b < (n-2) S/(n-1) \implies a+b > S/(n-1)$ holds because $(n-1)(a+b) > S$ is equivalent; small numeric checks, e.g., $n=3$, $a=1$, $b=2$, $c=2$, $S=5$, verify the inequality.

Lemma 2 is verified by explicitly subtracting sums of the other numbers, ensuring positivity of each term does not flip the inequality.

Alternative Approaches

One could attempt an induction on $n$. For $n=3$, the inequalities reduce to standard triangle inequalities; assuming the statements hold for $n-1$ numbers, one could add the $n$th number and check that the sum inequalities propagate. This is more cumbersome and requires careful tracking of all sums, while the direct approach using the sum $S$ and rearrangement of inequalities immediately establishes all claims. Another alternative is geometric visualization as a simplex in $\mathbb{R}^n$, but this adds abstraction without simplifying the arithmetic argument.