Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 7
Let $A = \lbrace a_0, a_1, … \rbrace$ be a sequence of real numbers and define the sequence $A' = {a_0', a_1', …}$ as follows for $n = 0, 1, …$: $a_{2n}' = a_n$, $a_{2n + 1}' = a_n + 1$. If $a_0 = 1$ and $A' = A$, find
- $a_1, a_2, a_3$ and $a_4$
- $a_{1981}$
- A simple general algorithm for evaluating $a_n$, for $n = 0, 1, …$
Hints
Hint for (a)
You can compute this with just the information given in the problem statement.
Hint for (b)
Did you get the pattern from (a)? You can just apply it for a number of steps to reach the answer.
Hint for (c)
To solve the general case, you need to find a pattern. Note that solutions to parts (a) and (b) ought to give you a hint as to what this might be. See if you can form a hypothesis and then use induction to prove it.
Solution
Open to see the solution to part (a); try solving it first or see the hints above!
Since $A' = A$ (given), we also know that $a'_i = a_i$ for all $i$, and therefore, we can also conclude that:
$$ \begin{align*} a_{2n} & = a_n \\ a_{2n+1} & = a_n + 1 \\ \end{align*} $$Another way to formuate this would be:
$$ \begin{equation*} a_i = \begin{cases} a_{\frac{i}{2}} & \text{ if } i \text{ is even} \\ a_{\frac{i-1}{2}} + 1 & \text{ if } i \text{ is odd} \\ \end{cases} \end{equation*} $$Here’s yet another alternative:
$$ \begin{equation*} a_{2i + k} = \begin{cases} a_{i} & \text{ if } k = 0 \\ a_{i} + 1 & \text{ if } k = 1 \\ \end{cases} \quad \text{where} \quad k \in \lbrace 0, 1 \rbrace \end{equation*} $$Let’s now compute $a_0, …, a_4$:
$$ \begin{align*} a_0 & = 1 & \quad \text{given} \\ a_1 & = a_0 + 1 = \boxed{2} & \quad \text{using above equations} \\ a_2 & = a_1 = \boxed{2} \\ a_3 & = a_1 + 1 = \boxed{3} \\ a_4 & = a_2 = a_1 = \boxed{2} \\ \end{align*} $$Open to see the solution to part (b); try solving it first or see the hints above!
First, read the introduction and solution to (a) above. Given the pattern, we can solve for $a_{1981}$:
$$ \begin{align*} a_{1981} & = a_{\frac{1980}{2}} + 1 = a_{990} + 1 \\ & = a_{\frac {990}{2}} + 1 = a_{495} + 1 \\ & = a_{\frac {494}{2}} + 1 + 1 = a_{247} + 2 \\ & = a_{\frac {246}{2}} + 1 + 2 = a_{123} + 3 \\ & = a_{\frac {122}{2}} + 1 + 3 = a_{61} + 4 \\ & = a_{\frac {60}{2}} + 1 + 4 = a_{30} + 5 \\ & = a_{\frac {30}{2}} + 5 = a_{15} + 5 \\ & = a_{\frac {14}{2}} + 1 + 5 = a_{7} + 6 \\ & = a_{\frac {6}{2}} + 1 + 6 = a_{3} + 7 \\ & = a_{\frac {2}{2}} + 1 + 7 = a_{1} + 8 \\ & = 2 + 8 = \boxed{10} \\ \end{align*} $$Open to see the solution to part (c); try solving it first or see the hints above!
Given the two rules in part (a) above, we can combine them to learn something else:
$$ \begin{align*} a_{2n+1} & = a_n + 1 & \\ a_{2n+1} & = a_{2n} + 1 & \qquad \textrm{given $a_{2n} = a_n$} \\ \end{align*} $$Thus, we know that:
- $a_n = a_{2n} = a_{4n} = … = a_{2^i n}$ → shows that multiplying $n$ by any power of $2$ has the same value of $a_n$
- $a_{2n+1} = a_{2n} + 1$ → this shows that numbers $a_i$ with an odd index $i$ are larger by $1$ than the preceding even-numbered index
Dividing by $2$ is equivalent to a right-shift of the binary representation by $1$ position. In binary representation, an even number is one that ends with $0$ and an odd number is one which has a $1$ in its last digit.
Similarly, for the odd numbers, we still right-shift by $1$, but we add $1$ to the value of the even $a_i$ that we compute recursively.
With $a_i$ with odd-valued indexes $i$ being just $1$ larger than the even number that precedes it, and with powers-of-two having $1$ or more trailing zeros in their binary representation, which can be removed by shifting right until there’s a $1$ in the last position, we can more clearly understand the algorithm.
Overall, we keep right-shifting the number if it’s even (has a $0$ as its last digit, so nothing to save) and we add $1$ to the tally if the number is odd (its last digit is $1$). Putting these steps together, we are counting the number of bits set to $1$ in the binary representation of $i$.
Thus, since we are given that $a_0 = 1$ and $0$ has no digits of $1$, we can see that:
$$ a_i = 1 + \lbrace \text{number of bits set to $1$ in the binary representation of $i$} \rbrace $$
For notational convenience, let’s define:
$$ \mathbf{N_1}(i) = \lbrace \text{number of bits set to 1 in the binary representation of $i$} \rbrace $$
and hence, we have:
$$ \boxed{a_i = 1 + \mathbf{N_1}(i)} $$
Using the subscript $2$ to describe binary representations, let’s validate this with the above numbers.
$$ \begin{align*} a_0 & = 1 + \mathbf{N_1}(0) = 1 + \mathbf{N_1}(0_2) = 1 + 0 = 1 \\ a_1 & = 1 + \mathbf{N_1}(1) = 1 + \mathbf{N_1}(1_2) = 1 + 1 = 2 \\ a_2 & = 1 + \mathbf{N_1}(2) = 1 + \mathbf{N_1}(10_2) = 1 + 1 = 2 \\ a_3 & = 1 + \mathbf{N_1}(3) = 1 + \mathbf{N_1}(11_2) = 1 + 2 = 3 \\ a_4 & = 1 + \mathbf{N_1}(4) = 1 + \mathbf{N_1}(100_2) = 1 + 1 = 2 \\ \end{align*} $$Let’s now try it for the large example above, namely $a_{1981}$:
$$ \begin{align*} & & a_{1981} & = & 1 + \mathbf{N_1}(1981) & = & 1 + \mathbf{N_1}(11110111101_2) & = & 1 + 9 & = 10 \\ & = & 1 + a_{990} & = & 1 + 1 + \mathbf{N_1}(990) & = & 1 + 1 + \mathbf{N_1}(1111011110_2) & = & 1 + 1 + 8 & = 10 \\ & = & 1 + a_{495} & = & 1 + 1 + \mathbf{N_1}(495) & = & 1 + 1 + \mathbf{N_1}(111101111_2) & = & 1 + 1 + 8 & = 10 \\ & = & 2 + a_{247} & = & 2 + 1 + \mathbf{N_1}(247) & = & 2 + 1 + \mathbf{N_1}(11110111_2) & = & 2 + 1 + 7 & = 10 \\ & = & 3 + a_{123} & = & 3 + 1 + \mathbf{N_1}(123) & = & 3 + 1 + \mathbf{N_1}(1111011_2) & = & 3 + 1 + 6 & = 10 \\ & = & 4 + a_{61} & = & 4 + 1 + \mathbf{N_1}(61) & = & 4 + 1 + \mathbf{N_1}(111101_2) & = & 4 + 1 + 5 & = 10 \\ & = & 5 + a_{30} & = & 5 + 1 + \mathbf{N_1}(30) & = & 5 + 1 + \mathbf{N_1}(11110_2) & = & 5 + 1 + 4 & = 10 \\ & = & 5 + a_{15} & = & 5 + 1 + \mathbf{N_1}(15) & = & 5 + 1 + \mathbf{N_1}(1111_2) & = & 5 + 1 + 4 & = 10 \\ & = & 6 + a_7 & = & 6 + 1 + \mathbf{N_1}(7) & = & 6 + 1 + \mathbf{N_1}(111_2) & = & 6 + 1 + 3 & = 10 \\ & = & 7 + a_3 & = & 7 + 1 + \mathbf{N_1}(3) & = & 7 + 1 + \mathbf{N_1}(11_2) & = & 7 + 1 + 2 & = 10 \\ & = & 8 + a_1 & = & 8 + 1 + \mathbf{N_1}(1) & = & 8 + 1 + \mathbf{N_1}(1_2) & = & 8 + 1 + 1 & = 10 \\ \end{align*} $$What’s interesting about this is that some CPU architectures have a dedicated instruction to counting the number of bits set to $1$ in a register, this is typically called “population count”, also referred to as Hamming weight and is used in chess engines, among many other use cases.
Let’s prove this solution inductively
We can prove that this is the correct formula by induction. Let’s recall the formula we’re trying to prove:
$$ a_n = 1 + \lbrace \text{number of bits set to $1$ in the binary representation of $n$} \rbrace $$
And we need to prove that given the general rule for computing $a_i$ above, the following is true:
$$ \begin{align*} a_{2n} & = a_n & \qquad \textrm{(1)} \\ a_{2n+1} & = a_n + 1 & \qquad \textrm{(2)} \\ \end{align*} $$Let’s consider the base case where $n = 0$:
$$ \begin{align*} a_{2n} & = a_n & \qquad \textrm{(1)} \\ a_{2 \cdot 0} & = a_0 & \qquad \textrm{substitute $n = 0$} \\ a_0 & = a_0 & \\ \end{align*} $$The first statement is trivially true. The second statement evaluates to:
$$ \begin{align*} a_{2n+1} & = a_n + 1 & \qquad \textrm{(2)} \\ a_{2 \cdot 0 + 1} & = a_0 + 1 & \qquad \textrm{substitute $n = 0$} \\ a_1 & = a_0 + 1 & \\ 1 + \mathbf{N_1}(1) & = 1+ \mathbf{N_1}(0) + 1 & \\ 1 + 1 & = 1 + 0 + 1 & \\ 2 & = 2 & \\ \end{align*} $$Which is also true.
Now, let’s assume this is true for $a_n$ and prove it for $a_{n+1}$. We have to consider two separate cases: one where $n$ is even, and one where $n$ is odd.
Inductive case when $n$ is even
Let’s first consider the case where $n$ is even. If $n$ is even, that means we can find $k$ such that $n = 2k$, and we have:
$$ \begin{align*} a_{2i} & = a_i & \qquad \textrm{(1) with substituting $n \rarr i$} \\ a_{2(n+1)} & = a_{n+1} & \qquad \textrm{substitute $i = n+1$} \\ a_{2n+2} & = a_{n+1} & \qquad \textrm{simplify} \\ 1 + \mathbf{N_1}(2n+2) & = 1 + \mathbf{N_1}(n+1) & \qquad \textrm{use formula} \\ \mathbf{N_1}(2n+2) & = \mathbf{N_1}(n+1) & \qquad \textrm{subtract $1$ from each side $(E_1)$} \\ \end{align*} $$Since $n$ is even, we know that $2n$ is divisible by $4$, so its binary representation is the same as $n$ but shifted over one digit, and it has 2 trailing zeroes: $…00$. Thus, when we add $2$ to $n$, we are just flipping the second-to-last $0$ to $1$, and hence, increasing the number of ones in the binary representation by $1$ (without affecting any other digits). Thus:
$$ \mathbf{N_1}(2n+2) = \mathbf{N_1}(2n) + 1 $$
Since $n$ is even, we know that $2n$ is just shifting the binary representation over by one digit, but not changing the number of ones, so using $\mathbf{N_1}(2n) = \mathbf{N_1}(n)$, thus:
$$ \mathbf{N_1}(2n+2) = \mathbf{N_1}(2n) + 1 = \mathbf{N_1}(n) + 1 $$
Additionally, since $n$ is even, its last digit must be $0$ so $n+1$ is simply flipping the last $0$ digit to $1$ without affecting any other digits, and hence, increasing its count of ones by $1$. This means that:
$$ \mathbf{N_1}(n+1) = \mathbf{N_1}(n) + 1 $$
And now we can prove the above statement $(E_1)$:
$$ \mathbf{N_1}(2n+2) = \mathbf{N_1}(2n) + 1 = \mathbf{N_1}(n) + 1 = \mathbf{N_1}(n+1) $$
Let’s now consider equation $(2)$:
$$ \begin{align*} a_{2k+1} & = a_k + 1 & \qquad \textrm{(2) with substituting $n \rarr k$} \\ a_{2(n+1) + 1} & = a_{n + 1} + 1 & \qquad \textrm{substitute $k = n + 1$} \\ a_{2n + 3} & = a_{n + 1} + 1 & \qquad \textrm{simplify} \\ 1 + \mathbf{N_1}(2n + 3) & = 1 + \mathbf{N_1}(n + 1) + 1 & \qquad \textrm{evaluate $a_i$} \\ \mathbf{N_1}(2n + 3) & = \mathbf{N_1}(n + 1) + 1 & \qquad \textrm{subtract $1$ from each side $(E_2)$} \\ \end{align*} $$Since $n$ is even, $2n$ is divisible by $4$, so the last two digits in the binary representation are $0$: $…00_2$. $3$ in binary is $11_2$, so adding $3$ to a number increases its count of ones by $2$:
$$ \mathbf{N_1}(2n + 3) = \mathbf{N_1}(2n) + 2 $$
Additionally, we also know that:
$$ \mathbf{N_1}(2n) = \mathbf{N_1}(n) $$
since the number of ones in a number doesn’t change when multiplying by $2$, and hence:
$$ \mathbf{N_1}(2n + 3) = \mathbf{N_1}(2n) + 2 = \mathbf{N_1}(n) + 2 $$
Similarly, since the binary representation of $1$ in binary is $1_2$, adding this to $n$ (which is even, and hence divisible by $2$), is just flipping the last digit from $0$ to $1$ and hence increasing its count of ones by $1$:
$$ \mathbf{N_1}(n + 1) = \mathbf{N_1}(n) + 1 $$
Thus, we can prove statement $(E_2)$ as follows:
$$ \begin{align*} \mathbf{N_1}(2n + 3) = \mathbf{N_1}(2n) + 2 = \mathbf{N_1}(n) + 2 = \left[ \mathbf{N_1}(n) + 1 \right] + 1 = \mathbf{N_1}(n + 1) + 1 \end{align*} $$This proves both equations when $n$ is even. We next consider the same equations when $n$ is odd.
Inductive case when $n$ is odd
Let’s consider equation $(1)$ when $n$ is odd:
$$ \begin{align*} a_{2i} & = a_i & \qquad \textrm{(1) with substituting $n \rarr i$} \\ a_{2(n+1)} & = a_{n+1} & \qquad \textrm{substitute $i = n+1$} \\ a_{2n+2} & = a_{n+1} & \qquad \textrm{simplify} \\ 1 + \mathbf{N_1}(2n+2) & = 1 + \mathbf{N_1}(n+1) & \qquad \textrm{use formula} \\ \mathbf{N_1}(2n+2) & = \mathbf{N_1}(n+1) & \qquad \textrm{subtract $1$ from each side $(O_1)$} \\ \end{align*} $$In this case, since $n$ is odd, we know that its binary representation must end in $1$: $…1_2$. Thus, when adding $1$ to it, there will be carryovers and some $1$s will turn to $0$s and vice versa. We don’t know what value $n$ has, so we can’t make a specific argument as to its value, or where the $1$s are located.
However, the interesting thing is that $2n$ has the same shape in terms of where the $0$s and $1$s are, they’re just shifted over by $1$ position to the left. Then, when we add $2$ to $2n$, we’re performing the same set of bit flips and carryovers as when adding $1$ to $n$.
Thus, the number of $1$s in $2n+2$ will the same as in $n+1$, and hence:
$$ \mathbf{N_1}(2n+2) = \mathbf{N_1}(n+1) $$
which proves $(O_1)$.
Let’s now consider the equation $(2)$ when $n$ is odd:
$$ \begin{align*} a_{2k+1} & = a_{k} + 1 & \qquad \textrm{(2) with substituting $n \rarr k$} \\ a_{2(n+1) + 1} & = a_{n+1} + 1 & \qquad \textrm{substitute $k = n + 1$} \\ a_{2n + 3} & = a_{n + 1} + 1 & \qquad \textrm{simplify} \\ 1 + \mathbf{N_1}(2n + 3) & = 1 + \mathbf{N_1}(n + 1) + 1 & \qquad \textrm{evaluate $a_i$} \\ \mathbf{N_1}(2n + 3) & = \mathbf{N_1}(n + 1) + 1 & \qquad \textrm{subtract $1$ from each side $(O_2)$} \\ \end{align*} $$Even though $n$ is odd, $2n$ is even, and it’s the same bit pattern as $n$, just shifted over $1$ position to the left, so it ends with: $…10_2$. Then, adding $3$ to it is doing both of the following:
- flipping the last digit from $0$ to $1$, increasing the number of ones by $1$
- flipping the second-to-last digit from $1$ to $0$ and carrying over the cascading change to the left
The first change is just adding $1$ to the total count. The second change is equivalent to adding $1$ to the value $n$, which means that:
$$ \mathbf{N_1}(2n + 3) = \mathbf{N_1}(n + 1) + 1 $$
which is exactly what we needed to show to prove statement $(O_2)$.
This completes the proof. $ \ \ \blacksquare $