Kvant Math Problem 569

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m25s
Source on kvant.digital

Problem

Several numbers are written in a notebook. One is allowed to append to these numbers a number equal to the arithmetic mean of two or more of them, provided it is different from all numbers already written. Prove that, starting with the two numbers 0 and 1, by means of the described operations one can obtain:

1. the number $\dfrac{1}{5}$;
2. any rational number between 0 and 1.

M. Serov

13th All-Union School Students' Olympiad, Grades 9 and 10

Exploration

Starting from $0$ and $1$, the first new number that can be obtained is $\frac12$, since the mean of $0$ and $1$ is $\frac12$.

Trying a few more operations,

$$\frac14=\frac{0+\frac12}{2},\qquad \frac34=\frac{\frac12+1}{2}.$$

Thus all dyadic fractions with denominator $2^n$ seem obtainable. The target $\frac15$ is not dyadic, so another idea is needed.

After obtaining $\frac14$, consider the mean of $0,\frac14,1$:

$$\frac{0+\frac14+1}{3}=\frac{5}{12}.$$

Then

$$\frac14=\frac{0+\frac12}{2},\qquad \frac13=\frac{0+\frac12+\frac12}{3}$$

would be impossible because repeated numbers are not available as separate entries. The operation uses written numbers, each at most once. Hence any argument relying on repetition is invalid.

A better approach is to examine what happens when a finite set of numbers already contains a complete arithmetic progression. Suppose

$$0,\frac1n,\frac2n,\ldots,\frac{n}{n}$$

have been obtained. The mean of

$$0,\frac1n,\ldots,\frac{n}{n}$$

equals

$$\frac{0+1+\cdots+n}{n+1}\cdot\frac1n = \frac{n(n+1)/2}{n(n+1)} = \frac12.$$

That does not create anything new.

Instead, if all fractions $k/n$ are available, then the mean of

$$\frac{i}{n},\frac{i+1}{n}$$

is

$$\frac{2i+1}{2n}.$$

Together with the old fractions, this gives every fraction with denominator $2n$. Hence from denominator $n$ one can pass to denominator $2n$.

To reach denominator $5$, one needs a way to pass from denominator $n$ to denominator $n+1$. Assume all fractions $k/n$ are present. The mean of all $n+1$ numbers

$$0,\frac1n,\ldots,\frac{n}{n}$$

is $\frac12$. More interestingly, for $k=0,\ldots,n$ the mean of the $n$ numbers

$$0,\frac1n,\ldots,\frac{n}{n}$$

with $\frac{k}{n}$ omitted equals

$$\frac{\frac{n+1}{2}-\frac{k}{n}}{n} = \frac{n(n+1)-2k}{2n^2}.$$

This does not immediately yield denominator $n+1$.

A more promising idea is to prove that whenever all fractions $k/n$ are available, one can obtain $\frac1{n+1}$. Indeed, the mean of

$$\frac1n,\frac2n,\ldots,\frac{n}{n}$$

is

$$\frac{1+2+\cdots+n}{n^2} = \frac{n+1}{2n}.$$

Since all fractions with denominator $2n$ are obtainable from the denominator-$n$ set, the number

$$\frac{n+1}{2n}$$

and also

$$\frac{n-1}{2n}$$

are available. Their mean is $\frac12$, so that does not help.

A different calculation is needed. Suppose all fractions $k/n$ are present. Then all fractions $m/(2n)$ are present. In particular,

$$\frac1{2n},\frac3{2n},\ldots,\frac{2n-1}{2n}$$

are present. The mean of these $n$ odd fractions is

$$\frac{1+3+\cdots+(2n-1)}{2n\cdot n} = \frac{n^2}{2n^2} = \frac12.$$

Again no gain.

The crucial observation is that if all fractions $k/n$ are available, then averaging all of them except $0$ gives

$$\frac{1+\cdots+n}{n\cdot n} = \frac{n+1}{2n},$$

and averaging all of them except $1$ gives

$$\frac{0+\cdots+(n-1)}{n\cdot n} = \frac{n-1}{2n}.$$

These two numbers are distinct. Their difference is

$$\frac1n.$$

This suggests encoding fractions through equally spaced points and generating finer subdivisions. The most likely hidden difficulty is proving rigorously that from all fractions $k/n$ one can generate all fractions $k/(n+1)$.

The right identity is

$$\frac{k}{n+1} = \frac1n\left(\frac{k}{n}\cdot\frac{n+1}{n+1}\right),$$

which is not directly expressible by averaging. A more structural viewpoint is needed.

Let $S_n={0,\frac1n,\ldots,1}$. If $S_n$ is available, then every midpoint between adjacent elements belongs to $S_{2n}$, hence $S_{2n}$ is available. Starting from $S_1={0,1}$, all dyadic grids $S_{2^m}$ are obtainable. Since $\frac15$ lies between $\frac18$ and $\frac14$, perhaps one can build denominator $5$ inside $S_8$. Experimentally,

$$\frac15=\frac{0+\frac18+\frac14+\frac38+\frac14}{5}$$

is invalid because repetitions are forbidden.

A direct construction is easier. From $0,1,\frac12,\frac14$ we obtain

$$\frac{0+\frac14+1}{3}=\frac5{12}.$$

Then

$$\frac{0+\frac14+\frac5{12}}{3}=\frac29.$$

The arithmetic becomes messy. A systematic invariant is preferable.

The natural invariant is that if all fractions with denominator $n$ are available, then averaging any subset corresponds to taking the average of distinct integers from ${0,\ldots,n}$ and dividing by $n$. Thus every number obtainable from $S_n$ has the form

$$\frac{t}{mn},$$

where $t$ is a sum of $m$ distinct integers between $0$ and $n$. A classical fact is that every integer between $0$ and $m n$ can be represented as such a sum when $m\le n+1$. Consequently every fraction with denominator $m n$ can be produced. Taking $m=n+1$ yields all fractions with denominator $n+1$.

This is the key.

Problem Understanding

We begin with the numbers $0$ and $1$. At each step we may append a new number equal to the arithmetic mean of any collection of at least two already written numbers, provided the resulting number has not appeared before.

We must prove first that $\frac15$ can be obtained, and second that every rational number in the interval $(0,1)$ can be obtained.

This is a Type D problem. We must show existence of a procedure producing the required numbers.

The core difficulty is to find a mechanism that systematically creates finer and finer rational subdivisions. The essential idea is to show that once all fractions

$$0,\frac1n,\ldots,\frac{n}{n}$$

are available, then all fractions

$$0,\frac1{n+1},\ldots,\frac{n+1}{n+1}$$

can also be obtained.

Proof Architecture

Lemma 1. If all numbers of the set $S_n={k/n:0\le k\le n}$ are available, then every number of the form $t/(mn)$ can be obtained whenever $0\le t\le mn$ and $1\le m\le n+1$.

Sketch. Represent $t$ as a sum of $m$ distinct integers from ${0,\ldots,n}$; the average of the corresponding fractions equals $t/(mn)$.

Lemma 2. Every integer $t$ with $0\le t\le mn$ can be represented as a sum of $m$ distinct integers from ${0,\ldots,n}$ whenever $1\le m\le n+1$.

Sketch. The sums of $m$ distinct integers range from $0+1+\cdots+(m-1)$ to $(n-m+1)+\cdots+n$, and every intermediate value occurs by a standard sliding argument.

Lemma 3. If $S_n$ is available, then $S_{n+1}$ is available.

Sketch. Apply Lemmas 1 and 2 with $m=n+1$.

The hardest point is Lemma 2, because it requires proving that every intermediate integer occurs as a sum of $m$ distinct numbers.

Solution

Let

$$S_n=\left{\frac{k}{n}:0\le k\le n\right}.$$

We shall prove by induction on $n$ that all numbers of $S_n$ can be obtained.

For $n=1$, the set $S_1={0,1}$ is exactly the initial set.

Assume that all numbers of $S_n$ have already been obtained.

Fix an integer $m$ with $1\le m\le n+1$. Consider any integer $t$ satisfying

$$0\le t\le mn.$$

We claim that $t$ can be written as a sum of $m$ distinct integers chosen from ${0,1,\ldots,n}$.

Indeed, let

$$a_1<a_2<\cdots<a_m$$

be such integers. The smallest possible sum is

$$0+1+\cdots+(m-1)=\frac{m(m-1)}2,$$

and the largest possible sum is

$$(n-m+1)+\cdots+n = mn-\frac{m(m-1)}2.$$

Starting from the minimal configuration

$$(0,1,\ldots,m-1),$$

increase the entries one by one while preserving strict inequalities. Every elementary increase raises the sum by exactly $1$. Since the set of admissible $m$-tuples is connected through such elementary moves, every integer between the minimal and maximal sums occurs as the sum of some admissible tuple.

For $t$ below the minimal sum, apply the same statement to

$$mn-t.$$

If

$$b_1+\cdots+b_m=mn-t,$$

then

$$(n-b_m)+\cdots+(n-b_1)=t,$$

and the numbers on the left are again distinct integers between $0$ and $n$.

Hence every integer $t$ with $0\le t\le mn$ is representable as a sum of $m$ distinct integers from ${0,\ldots,n}$.

Choose such a representation

$$t=i_1+\cdots+i_m.$$

Since all numbers $i_j/n$ belong to $S_n$, their arithmetic mean is

$$\frac1m\left(\frac{i_1}{n}+\cdots+\frac{i_m}{n}\right) = \frac{t}{mn}.$$

Therefore every fraction of the form

$$\frac{t}{mn}, \qquad 0\le t\le mn,$$

can be obtained.

Now take $m=n+1$. Then every fraction

$$\frac{t}{n(n+1)}, \qquad 0\le t\le n(n+1),$$

can be obtained. In particular, for each $k=0,1,\ldots,n+1$,

$$\frac{k}{n+1} = \frac{kn}{n(n+1)}$$

can be obtained. Thus every element of $S_{n+1}$ can be obtained.

The induction is complete. Consequently, for every positive integer $n$, all fractions

$$0,\frac1n,\frac2n,\ldots,\frac{n}{n}$$

can be obtained.

Taking $n=5$, we obtain $\frac15$.

Finally, let

$$r=\frac{a}{b}$$

be any rational number with $0<r<1$. Since all elements of $S_b$ are obtainable, the number

$$\frac{a}{b}=r$$

can be obtained.

Thus every rational number between $0$ and $1$ can be obtained. The required construction exists.

$$\boxed{\frac15\ \text{and, more generally, every rational number in }(0,1)\text{ can be obtained}.}$$

Verification of Key Steps

The first delicate point is the representation lemma. The admissible sums of $m$ distinct integers from ${0,\ldots,n}$ have minimum

$$\frac{m(m-1)}2$$

and maximum

$$mn-\frac{m(m-1)}2.$$

Every elementary move increases the sum by $1$, so no gaps can occur between these extremes. The symmetry

$$i\mapsto n-i$$

covers the values below the minimum threshold and confirms that every integer from $0$ to $mn$ is representable.

The second delicate point is the passage from a representation

$$t=i_1+\cdots+i_m$$

to the fraction $t/(mn)$. The operation allowed by the problem is precisely taking the arithmetic mean of distinct already written numbers. Averaging

$$\frac{i_1}{n},\ldots,\frac{i_m}{n}$$

gives

$$\frac{t}{mn},$$

which is exactly the required value.

The third delicate point is obtaining $S_{n+1}$ from $S_n$. Setting $m=n+1$ yields every fraction with denominator $n(n+1)$. Choosing

$$t=kn$$

produces

$$\frac{kn}{n(n+1)}=\frac{k}{n+1},$$

which establishes every element of $S_{n+1}$.

Alternative Approaches

One may view the numbers of $S_n$ as equally spaced points on the interval $[0,1]$. Averaging a subset of $S_n$ corresponds to averaging the associated integers from ${0,\ldots,n}$. The problem then becomes a statement about subset sums of consecutive integers. After proving that every integer in a suitable range is such a subset sum, the same induction $S_n\Rightarrow S_{n+1}$ emerges naturally.

Another approach uses combinatorial number theory. From $S_n$ one studies the set of all means of $m$ elements of $S_n$. These means are exactly the fractions $t/(mn)$ where $t$ is an $m$-term subset sum of ${0,\ldots,n}$. A theorem that these subset sums form a complete interval of integers immediately yields all fractions with denominator $n(n+1)$ and hence all fractions with denominator $n+1$. The inductive structure remains the same, but the subset-sum theorem is treated as a separate combinatorial result.