I've been practicing for the second round of the BMO and I've come across a question for which I think there must be a more efficient solution than I found.
Question 3:
https://bmos.ukmt.org.uk/home/bmo2-2011.pdf
To paraphrase the question, it asks for the number of positive integers $n < 2011$ such that $f(n) = f(2011) = 21$, where $f$ is defined on the positive integers as:
- $f(1) = 1$
- $f(4n) = f(2n)$
- $f(4n+1) = 2f(2n) + 1$
- $f(4n+2) = 2f(2n+1)$
- $f(4n+3) = f(2n+1)$
My method was to note that the only "path" to $21$ is $1,2,5,10,21$. The only positive ints that are mapped to $1$ are of the form $2^a – 1$, and so the only ints mapped to $2$ are of the form $2^b(2^a-1)$, and continuing in this fashion and expanding out, we have the only integers that map to $21$ are those of the form $2^{a+b+c+d+e}-2^{a+b+c+d}+2^{a+b+c}-2^{a+b}+2^e$, where $a,b,c,d,e \geq 1$.
So the number of solutions is equal to the number of sequences $y_1 > y_2 > y_3 > y_4 > y_5 \geq 1$ such that
$$ 2^{y_1} – 2^{y_2} + 2^{y_3} – 2^{y_4} + 2^{y_5} – 1 < 2011$$.
This in turn is equal to the number of sequences $x_1 > x_2 > x_3 > x_4 > x_5 \geq 0$ such that
$$ 2^{x_1} – 2^{x_2} + 2^{x_3} – 2^{x_4} + 2^{x_5} \leq 1005 $$.
Then I defined the function $F_k(n)$ as equal to the number of solutions to the more general problem, where the sum of powers must be $\leq n$ and there are $k$ variables instead of $5$, so the answer is $f_5(1005)$.
Because of the self similarity of the constraint, we have the following recurrence relation:
$$ F_k(n) = \sum_{m\geq 0}{F_{k-1}\left\lfloor\frac{n + (-1)^k2^m}{2^{m+1}}\right\rfloor} $$
With base cases of:
$$ F_1(n) = \lfloor \log_2{n} \rfloor $$
$$ F_k(n) = 0 \text{ when } n \leq 0$$
I implemented both the original problem and my solution in Python to check, and they both gave the same answer, $455$, so my solution is correct. However the paper is intended to be done without a calculator or computer, and it computing the desired value of $F$ by hand seems to need far too many calculations (these questions rarely require drawn out calculations).
So I assume that there is a more efficient method, either in calculating the values of $F$ or by looking at the problem from a completely different angle, both of which I would find extremely helpful.
Best Answer
Write everything in binary. Then we can see that $f(n)$ is the result when we collapse blocks of identical digits in $n$ to one such digit, e.g. $$f(2011)=f(11111011011_2)=10101_2=21.$$ So we want the number of $11$ bit numbers that have $5$ "switches" in the sequence of binary digits, and end in $1$. This is $\binom{11}{5}=462$. However, $7$ of these numbers are at least $2011$, so the final answer is $455$.