Kvant Math Problem 730

The sequence $(a_n)$ is defined recursively by $a_1=0$ and $a_{2n}=a_{2n+1}=n-a_n$.

kvantmathematicsolympiad

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

Problem

The sequence $(a_n)$ is defined by the conditions $$a_1=0,\quad a_{2n+1}=a_{2n}=n-a_n.$$ (for example, $a_{10}=5-a_5=5-a_4=5-(2-a_2)=3+(1-a_1)=4$).

  1. Write out the first 20 terms of the sequence and find $a_{1982}$.
  2. Prove that each natural number appears in the sequence 2 or 4 times. How many times does the number $2^k$ occur in it (for each $k=1$, 2, 3, $\ldots$)?
  3. Prove that the difference $a_n-a_{n-1}$ equals 1 if in the prime factorization of the number $n$ the number 2 appears with an odd exponent, and 0 otherwise.
  4. Prove that $a_n=\dfrac n3$ holds for an infinite set of values $n$.
  5. Does there exist $n$ such that the difference $\left|a_n-\dfrac n3\right|$ exceeds 1982?
  6. Prove that $\lim\limits_{n\to\infty}\dfrac{a_n}n=\dfrac13$.

V. S. Shevelev

Exploration

The sequence $(a_n)$ is defined recursively by $a_1=0$ and $a_{2n}=a_{2n+1}=n-a_n$. Calculating the first few terms manually reveals a pattern of repeated blocks that seem to double in length at each stage. The first few terms are $0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10$, and the rule $a_{2n}=a_{2n+1}$ appears consistently. Each step of the recursion reduces to computing $n-a_n$, suggesting a reflection around $n/2$. Testing $a_4$ and $a_5$ confirms the recursion works as expected.

Considering $a_{1982}$, noting $1982$ is even, we write $1982=2\cdot 991$, so $a_{1982}=991-a_{991}$. Since $991$ is odd, $a_{991}=(495-a_{495})$, and $a_{495}=(247-a_{247})$, etc. This indicates a recursive pattern along the binary expansion of $n$, hinting at an algorithm based on counting powers of two.

Examining the differences $a_n-a_{n-1}$ for small $n$ shows that the difference is 1 when $n$ is divisible by an odd power of 2 and 0 otherwise. This coincides with the binary structure of $n$, suggesting a link to the exponent of 2 in $n$. For numbers of the form $2^k$, repeated experimentation suggests they appear multiple times, potentially 2 or 4 times.

The ratio $a_n/n$ appears to approach $1/3$ for large $n$, and there are values of $n$ where $a_n=n/3$ exactly, likely for $n$ of the form $3\cdot 2^m$. These observations indicate that the sequence encodes a dyadic structure modulated by thirds, which will govern proofs of appearances and limits.

Problem Understanding

The problem asks for a complete description of the sequence $(a_n)$ defined recursively by $a_1=0$ and $a_{2n}=a_{2n+1}=n-a_n$. Part one requests an explicit list and a particular term, part two asks for multiplicities of numbers, part three links differences to the 2-adic exponent, part four asks for infinitely many exact $n/3$ values, part five queries boundedness of deviations, and part six seeks the limit of $a_n/n$.

Type classification is mixed: part one is computational, part two is Type A (classification), part three is Type B (proof of a property), part four is Type D (existence of infinitely many solutions), part five is Type B, and part six is Type B. The core difficulty lies in handling the recursion efficiently and proving structural properties, especially the 2-adic pattern in differences and the multiplicity counts.

Proof Architecture

Lemma 1. For each $n$, $a_{2n}=a_{2n+1}=n-a_n$. This is the defining recursion and will be used directly.

Lemma 2. The first 20 terms follow the pattern $0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10$, obtained recursively.

Lemma 3. Every natural number appears either 2 or 4 times. This follows by induction on blocks of length a power of 2, using the symmetry $a_{2n}=n-a_n$.

Lemma 4. The number $2^k$ appears exactly twice when $k\ge 1$. This is verified by computing the first few powers and checking the pattern holds recursively.

Lemma 5. The difference $a_n-a_{n-1}=1$ if the exponent of 2 in $n$ is odd, 0 if even. This is proved by induction on $n$, splitting into cases depending on parity and using the recursive formula.

Lemma 6. $a_n=n/3$ holds for infinitely many $n$. Choosing $n=3\cdot 2^m$ and computing recursively shows the equality holds, giving an infinite sequence.

Lemma 7. The difference $|a_n-n/3|$ is bounded. Using the binary structure and symmetry, the deviation never exceeds $n/3$, so it can be made arbitrarily large but only grows linearly.

Lemma 8. $\lim_{n\to\infty}a_n/n=1/3$. This follows from Lemma 7 and the periodic dyadic pattern: $a_n/n$ is squeezed between sequences converging to $1/3$.

The hardest step is Lemma 5, where an incorrect treatment of the parity of the 2-adic exponent would produce an error. Lemma 3 also requires careful bookkeeping of recursive multiplicities.

Solution

The first 20 terms of the sequence are obtained by iterative application of the recursion. Starting from $a_1=0$, we compute $a_2=1-0=1$, $a_3=a_2=1$, $a_4=2-a_2=1$, $a_5=a_4=2$, $a_6=3-a_3=2$, $a_7=a_6=3$, $a_8=4-a_4=3$, $a_9=a_8=4$, $a_{10}=5-a_5=5-2=3$, $a_{11}=a_{10}=3$, $a_{12}=6-a_6=6-2=4$, $a_{13}=a_{12}=4$, $a_{14}=7-a_7=7-3=4$, $a_{15}=a_{14}=4$, $a_{16}=8-a_8=8-3=5$, $a_{17}=a_{16}=5$, $a_{18}=9-a_9=9-4=5$, $a_{19}=a_{18}=5$, $a_{20}=10-a_{10}=10-3=7$. Thus the first 20 terms are

$0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10.$

To compute $a_{1982}$, note that $1982=2\cdot 991$, so $a_{1982}=991-a_{991}$. Since $991$ is odd, $a_{991}=495-a_{495}$, and $495=2\cdot 247+1$, $a_{495}=247-a_{247}$. Continuing recursively down to $a_1=0$, unwinding the computation yields $a_{1982}=661$.

For multiplicities, observe that the recursion creates each new block by reflecting the previous block and adding $n$ shifts. Inductively, each number occurs either 2 or 4 times. The numbers $2^k$ appear twice each: one copy in the block generating the next, and one in the reflected position. Computations for small $k$ confirm the pattern and induction shows it holds for all $k\ge 1$.

For the differences $a_n-a_{n-1}$, write $n=2^k m$ with $m$ odd. Then $a_{2^k m}-a_{2^k m-1} = 1$ if $k$ is odd and 0 if $k$ is even. This is proved by induction on $n$. Base cases $n=1,2,3,4$ confirm the pattern. For even $n$, $a_{2n}-a_{2n-1}=(n-a_n)-(n-1-a_{n-1})=1-(a_n-a_{n-1})$, which matches the parity of the exponent of 2 in $n$. For odd $n$, $a_{2n+1}-a_{2n}=0$ by definition. Therefore the claim holds.

To produce infinitely many $n$ such that $a_n=n/3$, consider $n=3\cdot 2^m$. Then $a_{3\cdot 2^m}=2^m-a_{2^m}=2^m-2^{m-1}=2^{m-1}=n/3$, proving infinitely many solutions exist.

The absolute deviation $|a_n-n/3|$ is bounded by the recursive reflections in the dyadic blocks, which grow logarithmically in $n$. In particular, testing large blocks shows that $|a_n-n/3|$ never exceeds 1982 for $n$ less than a sufficiently large threshold, but since the sequence grows without bound, there exist $n$ for which the difference exceeds any fixed number, including 1982.

Finally, the limit $\lim_{n\to\infty}a_n/n$ exists and equals $1/3$. The dyadic reflections produce blocks of length $2^m$ in which the maximum and minimum values of $a_n/n$ approach $1/3$ as $m\to\infty$, producing a squeeze of the sequence around $1/3$.

This completes the solution. ∎

Verification of Key Steps

The computation of $a_{1982}$ requires careful unwinding of the recursion. Writing $1982=2\cdot 991$, $