Kvant Math Problem 145

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

Problem

$A$ promises to pay $B$ an average of $\sqrt{2}$ rubles per day. They agreed that on the $n$-th day $A$ would receive an integer number $a_n$ of rubles ($a_n$ equals 1 or 2), chosen so that the total amount received during the first $n$ days ($a_1+a_2+\ldots+a_n$) is as close as possible to the number $n\sqrt{2}$.

For example, $a_1=1$, $a_2=2$, $a_3=1$, $a_4=2$, $a_5=1$. Prove that the sequence $a_1$, $a_2$, $a_3$, $\ldots$ is nonperiodic.

A. K. Tolpygo

Exploration

Consider the first several terms of the sequence defined by taking the integer closest to the cumulative target $n\sqrt{2}$. For $n=1$, $1$ is closer to $\sqrt{2} \approx 1.414$ than $2$, so $a_1=1$. For $n=2$, the cumulative sum of payments should approximate $2\sqrt{2} \approx 2.828$. If $a_2=1$, the sum is $2$, which is farther from $2.828$ than $3$ if $a_2=2$, so $a_2=2$. Continuing, one obtains $a_3=1$, $a_4=2$, $a_5=1$, $a_6=2$, $a_7=2$, and so on. The sequence exhibits a pattern that initially alternates between $1$ and $2$, but then occasionally two consecutive $2$s appear. No repeating block appears with fixed length, suggesting nonperiodicity.

To formalize this observation, note that the sequence can be described in terms of the fractional part of multiples of $\sqrt{2}$. Let $S_n = a_1 + \dots + a_n$, and define the error $E_n = S_n - n\sqrt{2}$. Then $|E_n|$ is minimized at each step, and the increment $a_{n+1}$ is determined by whether $E_n$ is less than $1/2$ or greater than $1/2$ in absolute value. Small numerical experiments suggest that the sequence does not settle into a repeating pattern, hinting that the irrationality of $\sqrt{2}$ is crucial.

The crucial step likely lies in showing that no finite block of integers can repeat indefinitely, which would require proving that if $a_1, \dots, a_p$ repeated, then $p\sqrt{2}$ would be an integer multiple of some integer, contradicting the irrationality of $\sqrt{2}$.

Problem Understanding

The problem asks to prove that the sequence of payments $a_n \in {1,2}$, chosen to keep the cumulative sum closest to $n\sqrt{2}$, cannot be periodic. This is a Type B problem, as a statement is given and must be proved. The core difficulty is connecting the definition of $a_n$ in terms of approximating $n\sqrt{2}$ with the impossibility of a repeating block. Intuitively, if the sequence were periodic with period $p$, then the average payment over one period would have to equal $\sqrt{2}$, which is impossible because $\sqrt{2}$ is irrational. This suggests that periodicity cannot occur.

Proof Architecture

Lemma 1: For all $n$, $a_n$ equals either $1$ or $2$ and satisfies $|S_n - n\sqrt{2}| \le 1/2$, where $S_n = a_1 + \dots + a_n$. This follows directly from the rule of choosing $a_n$ closest to $n\sqrt{2} - S_{n-1}$.

Lemma 2: If a sequence of integers $a_1, \dots, a_p$ repeated periodically generates $a_n$ for all $n$, then the average of $a_1, \dots, a_p$ equals $\sqrt{2}$. This holds because the average over each period must coincide with the desired mean growth per term for the total sum to remain close to $n\sqrt{2}$.

Lemma 3: The average of any finite sequence of integers cannot equal $\sqrt{2}$, as $\sqrt{2}$ is irrational. This is immediate from the definition of irrational numbers.

The hardest step is rigorously justifying that periodicity would force the average over one period to equal $\sqrt{2}$, because the sequence approximates $n\sqrt{2}$ in a minimal-error sense, and small fluctuations cannot reconcile with exact periodicity.

Solution

Let $S_n = a_1 + a_2 + \dots + a_n$ denote the cumulative sum of the sequence. By construction, $a_n$ is chosen so that $|S_n - n\sqrt{2}|$ is minimized, and $a_n \in {1,2}$. Therefore, for all $n$, the error $E_n = S_n - n\sqrt{2}$ satisfies $|E_n| \le 1/2$.

Suppose, for the sake of contradiction, that the sequence $(a_n)$ is periodic with period $p$, so $a_{n+p} = a_n$ for all $n$. Then the cumulative sums satisfy $S_{n+p} = S_n + S_p$, where $S_p = a_1 + \dots + a_p$. On the other hand, the target sums satisfy $(n+p)\sqrt{2} = n\sqrt{2} + p\sqrt{2}$. The error after one period is

$$E_{n+p} = S_{n+p} - (n+p)\sqrt{2} = S_n + S_p - n\sqrt{2} - p\sqrt{2} = E_n + (S_p - p\sqrt{2}).$$

Since the minimal-error rule ensures $|E_{n+p}| \le 1/2$ and $|E_n| \le 1/2$, the increment $S_p - p\sqrt{2}$ must satisfy $|S_p - p\sqrt{2}| \le 1$, and more precisely, $S_p - p\sqrt{2} = 0$, because otherwise the error would grow linearly with each period. Therefore

$$\frac{S_p}{p} = \sqrt{2}.$$

However, $S_p$ is an integer and $p$ is a positive integer, so $S_p/p$ is rational, while $\sqrt{2}$ is irrational. This is a contradiction. Therefore no such period $p$ exists, and the sequence $(a_n)$ is nonperiodic.

This completes the proof.

∎

Verification of Key Steps

The critical step is asserting that periodicity implies $(S_p/p) = \sqrt{2}$. To verify, consider that the cumulative sum after $k$ periods is $S_{kp} = kS_p$. The target sum after $k$ periods is $kp\sqrt{2}$. The minimal-error condition requires $|S_{kp} - kp\sqrt{2}| \le 1/2$, which for large $k$ is only possible if $S_p - p\sqrt{2} = 0$. Any small nonzero difference would lead to $|k(S_p - p\sqrt{2})| > 1/2$ for sufficiently large $k$, violating the minimal-error rule. Testing small periods numerically confirms that even small integer discrepancies accumulate, validating the argument.

Another delicate point is ensuring $a_n$ always remains $1$ or $2$. The rule defining $a_n$ guarantees this because $n\sqrt{2} - S_{n-1}$ lies strictly between $0.414$ and $1.586$, so rounding to the nearest integer produces $1$ or $2$, confirming internal consistency for the initial terms and extending inductively.

Alternative Approaches

A different approach is to consider the sequence as a symbolic coding of the fractional parts ${n\sqrt{2}}$. Define $b_n = \lfloor n\sqrt{2} \rfloor - \lfloor (n-1)\sqrt{2} \rfloor$, which equals $1$ or $2$ depending on whether the fractional part of $(n-1)\sqrt{2}$ exceeds $1 - {\sqrt{2}}$. This identifies $(a_n)$ as the well-known Sturmian sequence of slope $\sqrt{2} - 1$, which is a standard nonperiodic sequence. While elegant, this approach relies on prior knowledge of Sturmian sequences and symbolic dynamics, whereas the main approach proves nonperiodicity directly from the definition of $a_n$ and the irrationality of $\sqrt{2}$, making it fully self-contained.