Kvant Math Problem 521

Consider the first few values of $a_n$.

kvantmathematicsolympiad

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

Problem

Let $a_n$ denote the integer nearest to $\sqrt{n}$. Find the sum $$\dfrac1{a_1}+\dfrac1{a_2}+\dfrac1{a_3}+\ldots+\dfrac1{a_{1980}}.$$

G. A. Gurevich

All-Union Mathematical Olympiad for School Students (XII, 1978, Grades 8–9)

Exploration

Consider the first few values of $a_n$. For $n = 1$, $\sqrt{1} = 1$, so $a_1 = 1$. For $n = 2$, $\sqrt{2} \approx 1.414$, rounding to the nearest integer gives $a_2 = 1$. For $n = 3$, $\sqrt{3} \approx 1.732$, so $a_3 = 2$. For $n = 4$, $\sqrt{4} = 2$, giving $a_4 = 2$. For $n = 5$, $\sqrt{5} \approx 2.236$, so $a_5 = 2$. For $n = 6$, $\sqrt{6} \approx 2.449$, $a_6 = 2$. For $n = 7$, $\sqrt{7} \approx 2.646$, $a_7 = 3$. For $n = 8$, $\sqrt{8} \approx 2.828$, $a_8 = 3$. For $n = 9$, $\sqrt{9} = 3$, $a_9 = 3$. Continuing in this way, each integer $k$ appears as $a_n$ multiple times for consecutive $n$ before $a_n$ jumps to $k+1$. This suggests the sum can be grouped according to the value of $a_n$, counting how many times each integer occurs, which is likely related to the squares $k^2$ and $(k+1)^2$.

The crucial point is to determine exactly how many integers $n$ correspond to a given $a_n = k$, especially near the boundaries where $\sqrt{n}$ is halfway between two integers. Errors are likely to occur in these rounding thresholds.

Problem Understanding

The problem asks for the sum of the reciprocals of the integers nearest to $\sqrt{n}$ for $n$ from $1$ to $1980$. This is a Type C problem because it asks for the exact value of a finite sum. The core difficulty lies in counting correctly how many terms correspond to each integer value of $a_n$. Intuitively, $a_n = k$ for integers $n$ in the interval $[(k - \tfrac12)^2, (k + \tfrac12)^2)$, except adjustments must be made for small $k$ where $k - \tfrac12 < 1$. This interval length determines the number of times each reciprocal $1/k$ appears.

Proof Architecture

Lemma 1: For each integer $k \ge 1$, $a_n = k$ if and only if $n$ satisfies $k - \frac12 \le \sqrt{n} < k + \frac12$, that is, $n \in [(k - \frac12)^2, (k + \frac12)^2)$. This follows directly from the definition of nearest integer rounding.

Lemma 2: The number of integers $n$ satisfying $a_n = k$ is $2k$ for $k \ge 2$ and $1$ for $k=1$. This is obtained by computing the integer count in the interval $[(k - \frac12)^2, (k + \frac12)^2)$.

Lemma 3: Determine the largest integer $m$ such that $(m + \tfrac12)^2 \le 1980$ to identify the last full block of terms with $a_n = m$. This involves explicit calculation and ensures all $n \le 1980$ are covered.

Lemma 4: Sum the contributions of each block $1/k$ multiplied by the number of times it occurs. For the last partial block, only include terms with $n \le 1980$.

The hardest step is Lemma 2, because miscounting the interval length or the rounding rules will give an incorrect sum. Lemma 3 also requires careful arithmetic to avoid off-by-one errors.

Solution

Consider the definition $a_n$ as the nearest integer to $\sqrt{n}$. Then $a_n = k$ if and only if

$$k - \frac12 \le \sqrt{n} < k + \frac12.$$

Squaring both sides gives

$$(k - \frac12)^2 \le n < (k + \frac12)^2.$$

For $k = 1$, $(1 - \frac12)^2 = \frac14$, but $n \ge 1$, so the first interval is $n \in [1, \frac{9}{4})$, that is, $n = 1, 2$. Checking these, $a_1 = 1$, $a_2 = 1$. Thus, $1$ appears twice, but we must be precise: $n=1,2$ correspond to $a_n = 1$ because $\sqrt{2} \approx 1.414 < 1.5$.

For $k \ge 2$, the interval length is $(k + \frac12)^2 - (k - \frac12)^2 = (k^2 + k + \frac14) - (k^2 - k + \frac14) = 2k$. Therefore, for each $k \ge 2$, there are exactly $2k$ consecutive integers $n$ such that $a_n = k$.

Let $m$ be the largest integer such that $(m + \frac12)^2 \le 1980$. Compute $(m + \frac12)^2 = 1980$ approximately. Since $44^2 = 1936$ and $45^2 = 2025$, $(44 + \frac12)^2 = 44.5^2 = 1980.25 > 1980$, so $m = 44$. Therefore, $a_n = k$ for $k = 1, 2, \dots, 43$ each appearing exactly $2k$ times, and $a_n = 44$ for $n$ from $(43.5)^2 = 1892.25$ up to $1980$. The number of integers in this last block is $1980 - 1892 = 88$.

The sum is therefore

$$\sum_{k=1}^{43} 2k \cdot \frac{1}{k} + 88 \cdot \frac{1}{44} = \sum_{k=1}^{43} 2 + 2 = 86 + 2 = 88.$$

Explicitly, $\sum_{k=1}^{43} 2 = 86$, and the last contribution is $88/44 = 2$, giving a total of $88$.

Hence the sum is

$$\boxed{88}.$$

Verification of Key Steps

The interval length formula $(k + \frac12)^2 - (k - \frac12)^2 = 2k$ was recomputed explicitly for $k = 2,3,4$ and verified: for $k=2$, $(2.5)^2 - (1.5)^2 = 6.25 - 2.25 = 4 = 2 \cdot 2$, for $k=3$, $(3.5)^2 - (2.5)^2 = 12.25 - 6.25 = 6 = 2 \cdot 3$. The largest $m$ was recalculated: $(44.5)^2 = 1980.25 > 1980$, $(43.5)^2 = 1892.25 < 1980$, confirming $m = 44$. The last block length $1980 - 1892 = 88$ was double-checked. Each step reproduces the sum $88$ precisely, confirming the arithmetic and the rounding boundaries are correct.

Alternative Approaches

An alternative approach would be to approximate the sum using an integral, interpreting $1/a_n \approx 1/\sqrt{n}$ and summing over $n$ to estimate the value. This would provide an approximate answer but would fail to yield the exact integer $88$ because rounding effects accumulate and the last partial interval requires exact counting. The main approach is preferable because it provides an exact enumeration of terms and rigorously accounts for the rounding rules.