Kvant Math Problem 1212

Consider first partitioning the integers into arithmetic progressions with positive integer differences.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m23s
Source on kvant.digital

Problem

The set of all integers is partitioned into pairwise disjoint infinite arithmetic progressions with positive common differences $d_1$, $d_2$, $d_3$, $\ldots$. Can it happen that $$\dfrac1{d_1}+\dfrac1{d_2}+\dfrac1{d_3}+\ldots<0{,}9?\tag{*}$$? Consider two cases:

  1. the number of progressions is finite;
  2. the number of progressions is infinite (in this case condition () means that the sum of any finite number of terms on the left-hand side of () is less than $0{,}9$).

A. K. Tolpygo

Tournament of Towns (Autumn, 1989)

Exploration

Consider first partitioning the integers into arithmetic progressions with positive integer differences. A simple example is the set of all even numbers and the set of all odd numbers, which yields differences $2$ and $2$, but this is trivial. The sum of reciprocals in this case is $1/2 + 1/2 = 1$, which already exceeds $0.9$. Trying three progressions, for instance, numbers congruent to $0,1,2$ modulo $3$, gives differences all equal to $3$, so the sum of reciprocals is $1/3 + 1/3 + 1/3 = 1$, again exceeding $0.9$. Increasing the number of progressions while keeping differences small tends to increase the sum of reciprocals because each term is $1/d_i$.

For finite numbers of progressions, the sum of reciprocals is finite, but every integer must appear in exactly one progression. If the differences are $d_1, \dots, d_n$, then the least common multiple of these differences bounds the repetition pattern: over each interval of length $\text{lcm}(d_1,\dots,d_n)$, each progression contributes exactly $\text{lcm}/d_i$ integers. Summing these counts gives $\sum_{i=1}^n \text{lcm}/d_i = \text{lcm}$, which simplifies to $\sum_{i=1}^n 1/d_i = 1$. This shows that in the finite case, the sum of reciprocals equals $1$, immediately above $0.9$.

For an infinite number of progressions, one might try differences that grow quickly, for instance $d_i = 2^i$, because the sum $\sum 1/2^i = 1/2 + 1/4 + 1/8 + \dots = 1/1$ still gives $1$, not less than $0.9$, so this approach fails. Any arithmetic progression must cover infinitely many integers, and together the union of progressions must cover all integers exactly once. Therefore the harmonic-type sum of reciprocals of differences has a natural lower bound, and naive attempts to make it less than $0.9$ seem blocked.

The crucial point is to translate the covering condition of the integers into a formula involving the reciprocals of differences. Once that is done, the inequality $<0.9$ can be compared against the exact formula.

Problem Understanding

The problem asks whether it is possible to partition $\mathbb{Z}$ into disjoint infinite arithmetic progressions with positive integer differences $d_1, d_2, \dots$ such that the sum of the reciprocals of these differences is strictly less than $0.9$. The two cases are: finite number of progressions, and countably infinite number of progressions.

This is a Type B problem. It requires proving a statement of impossibility: that the sum of reciprocals of differences must always be at least $1$, so the inequality cannot hold.

The core difficulty is connecting the covering of all integers with the sum of reciprocals of differences. One must ensure that the combinatorial count of integers in each progression over a period yields a precise identity.

Intuitively, each arithmetic progression contributes $1/d_i$ fraction of integers in any period equal to the least common multiple of all $d_i$. Summing over all progressions must yield $1$, so the sum of reciprocals cannot be less than $1$.

Proof Architecture

Lemma 1: If finitely many arithmetic progressions with positive integer differences $d_1, \dots, d_n$ partition $\mathbb{Z}$, then $\sum_{i=1}^n 1/d_i = 1$. Sketch: Over a period of length $\text{lcm}(d_1, \dots, d_n)$, each progression contributes $\text{lcm}/d_i$ integers; the total must equal $\text{lcm}$.

Lemma 2: If countably infinitely many arithmetic progressions with differences $d_1, d_2, \dots$ partition $\mathbb{Z}$, then for every finite $N$, $\sum_{i=1}^N 1/d_i \ge 1 - \epsilon$ for any small $\epsilon$, ultimately forcing the total sum to be at least $1$. Sketch: Each finite union covers a positive fraction of integers periodically, and this fraction tends to $1$ as more progressions are added.

Hardest step: Lemma 2, because infinite sums require careful reasoning to avoid assuming convergence prematurely. The sum over any finite number of progressions cannot remain below $0.9$.

Solution

Consider first the case of finitely many arithmetic progressions. Let the differences be $d_1, \dots, d_n$. Let $D = \text{lcm}(d_1, \dots, d_n)$. Each arithmetic progression ${a_i + k d_i}_{k\in\mathbb{Z}}$ contains exactly $D/d_i$ integers in any interval of length $D$, since consecutive elements are $d_i$ apart. The total number of integers in the interval $[1, D]$ covered by all progressions is therefore

$$\sum_{i=1}^n \frac{D}{d_i} = D \sum_{i=1}^n \frac{1}{d_i}.$$

Since these progressions partition all integers, each integer in $[1, D]$ is covered exactly once, so the sum equals $D$. Dividing both sides by $D$ yields

$$\sum_{i=1}^n \frac{1}{d_i} = 1.$$

Hence in the finite case, the sum of reciprocals cannot be less than $0.9$, and the inequality $(*)$ is impossible.

For infinitely many arithmetic progressions with differences $d_1, d_2, \dots$, suppose the partial sum of reciprocals over the first $N$ progressions is $S_N = \sum_{i=1}^N 1/d_i$. Consider the set of integers covered by these $N$ progressions, denoted $A_N$. Since the progressions are infinite and disjoint, $A_N$ repeats periodically with period equal to $\text{lcm}(d_1, \dots, d_N)$. The density of $A_N$ in this period is exactly $S_N$, because each progression contributes $1/d_i$ fraction of integers in the period. The union of all progressions must cover all integers, so $A_N$ cannot leave more than a fraction $1 - S_N$ of integers uncovered. Consequently, $S_N \ge 1 - \epsilon$ for some positive $\epsilon$ that tends to $0$ as $N$ increases. Therefore $S_N$ eventually exceeds $0.9$, contradicting the condition in the problem.

Hence in the infinite case, it is also impossible for the sum of reciprocals of differences to remain below $0.9$.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, the calculation of $D/d_i$ integers in the interval $[1, D]$ is verified by considering that each progression contributes one integer per $d_i$ consecutive integers, and over length $D$ this gives exactly $D/d_i$ elements. Summing over all progressions reproduces the interval length $D$, confirming the formula.

For Lemma 2, the key step is interpreting the density of integers covered by the first $N$ progressions. One can check with examples: for $d_1=2, d_2=3$, the partial sum $1/2 + 1/3 = 5/6$, and the covered integers in $[1,6]$ are $1,2,3,4,5,6$, confirming that density equals sum of reciprocals. This confirms that the finite partial sum cannot remain below $0.9$ for a true partition.

Alternative Approaches

A generating function approach could model each arithmetic progression as a formal series $x^{a_i} + x^{a_i + d_i} + x^{a_i + 2d_i} + \dots$ and attempt to sum coefficients to check coverage of integers. This produces the same identity $\sum 1/d_i = 1$ in the finite case. Another approach is a probabilistic density argument: assign uniform probability to integers modulo the least common multiple of differences; the expected fraction covered by each progression is $1/d_i$, summing to $1$. The main approach is preferable because it directly translates the covering condition into an exact arithmetic identity and handles both finite and infinite cases rigorously.