IMO 1996 SL A9

Origin: POL | Category: Algebra

Problem

Let the sequence $a(n)$, $n = 1, 2, 3, \dots$, be generated as follows:

$a(1) = 0$, and for $n > 1$,

$$a(n) = a\bigl(\lfloor n/2 \rfloor\bigr) + (-1)^n \frac{n(n+1)}{2}.$$

(Here $\lfloor t \rfloor$ denotes the greatest integer $\leq t$.)

(a) Determine the maximum and minimum value of $a(n)$ over $n \leq 1996$ and find all $n \leq 1996$ for which these extreme values are attained.

(b) How many terms $a(n)$, $n \leq 1996$, are equal to $0$?

Solution

From the definition of $a(n)$ we obtain

$$a(n) - a(\lfloor n/2 \rfloor) = \begin{cases} 1 & \text{if } n \equiv 0 \text{ or } n \equiv 3 \pmod 4,\ -1 & \text{if } n \equiv 1 \text{ or } n \equiv 2 \pmod 4. \end{cases}$$

Let $n = b_k b_{k-1} \dots b_1 b_0$ be the binary representation of $n$, where we assume $b_k = 1$. If we define $p(n)$ and $q(n)$ to be the number of indices $i = 0, 1, \dots, k-1$ with $b_i = b_{i+1}$ and the number of $i = 0, 1, \dots, k-1$ with $b_i \neq b_{i+1}$ respectively, we get

$$a(n) = p(n) - q(n). \tag{1}$$

(a) The maximum value of $a(n)$ for $n \leq 1996$ is $9$ when $p(n) = 9$ and $q(n) = 0$, i.e., in the case $n = 1111111111_2 = 1023$.

The minimum value is $-10$ and is attained when $p(n) = 0$ and $q(n) = 10$, i.e., only for $n = 10101010101_2 = 1365$.

(b) From (1) we have that $a(n) = 0$ is equivalent to $p(n) = q(n) = k/2$. Hence $k$ must be even, and the $k/2$ indices $i$ for which $b_i = b_{i+1}$ can be chosen in exactly

$$\binom{k}{k/2}$$

ways. Thus the number of positive integers $n < 2^{11} = 2048$ with $a(n) = 0$ is equal to

$$\binom{0}{0} + \binom{2}{1} + \binom{4}{2} + \binom{6}{3} + \binom{8}{4} + \binom{10}{5} = 351.$$

But five of these numbers exceed $1996$: these are

$2002 = 11111010010_2$, $2004 = 11111010100_2$, $2006 = 11111010110_2$, $2010 = 11111011010_2$, $2026 = 11111101010_2$.

Therefore, there are $346$ numbers $n \leq 1996$ for which $a(n) = 0$.