BdMO National Secondary 2020 P11

[Mursalin]

উর্মি কম্পিউটারে একটা গেইম খেলছে। যদি কম্পিউটার স্ক্রিনে $x$ সংখ্যাটা দেখা যায়, তাহলে পরের চালে সে দুটো কাজ করতে পারবে।

1. সে হয় $x$-কে $4x+1$ দিয়ে পাল্টে দিতে পারবে
2. অথবা সে $x$-কে $\frac{x}{2}$-এর চেয়ে বড় না এমন সবচেয়ে বড় পূর্ণসংখ্যা দিয়ে পাল্টে দিতে পারবে

স্ক্রিনে শুরুতে $0$ সংখ্যাটা ছিল। শুন্য বা তার চেয়ে বেশি সংখ্যক চাল দিয়ে $2020$-এর চেয়ে বড় না এমন কতগুলো পূর্ণসংখ্যায় উর্মি পৌঁছাতে পারবে? কোনো একটা সংখ্যায় পৌঁছাতে গিয়ে যদি মাঝে $2020$-এর চেয়ে বড় কিছু এসে পড়ে, তাহলে অসুবিধা নেই।

-----

Urmi is playing a game on a computer. If the computer screen displays the number $x$, then in the next move, Urmi can do one of the following:

1. Replace $x$ by $4x + 1$
2. Replace $x$ by the largest integer not greater than $\frac{x}{2}$

Initially the computer screen displays $0$. How many different integers less than or equal to $2020$ can Urmi achieve through a sequence of moves? It is permitted for the number displayed on the screen to exceed $2020$ during the sequence.

[Anindya Biswas]

Let $f(x)=4x+1$ and $g(x)=\lfloor \frac{x}{2} \rfloor$.
Now, in the binary representation of a number, the operation $f$ just adds $01$ to the tail of that binary string, and the operation $g$ removes the last bit of that string.
For example: $f(101011)=10101101$ and $g(101011)=10101$.
So, if a number $n$ is achievable by applying $f$ and $g$ on $0$, then this number cannot contain two consecutive $1$s in its binary representation.
Because $g$ only removes the last bit. And the only way to add a new bit is to use $f$. But applying $f$ adds $01$ which means you must have at least one $0$ before you can add $1$. So, it is not possible to have two consecutive $1$s.
Now let $h(x)=g\left(f(x)\right)$. Notice that by applying $h$, we can add a zero to the end of a string. So, by applying $h$, $n-1$ times on a number, and then applying $f$, we can add $n$ $0$s and then $1$.
From this observation, it is now clear that every positive integer whose binary representation doesn't contain consecutive $1$s can be achieved by applying $f$ and $h$.
Now, $2020=11111100100_2$, which is a binary string of $11$ bits. The largest achievable $11$ bit long string is $10101010101$ which is less than $2020$. So, it is sufficient to count the number of achievable strings upto $11$ bits.
Now let $a_k$ be the number of achievable numbers from $2^{k-1}$ to $2^k-1$. Which is the number of achievable strings of length $k$. [We are not counting $0$ as a length $1$ bynary string for now.]
Notice that $a_1=1$, $a_2=1$. and $a_n=1+a_1+a_2+\cdots+a_{n-2}$ [By counting all the sub-strings of length $1$ to $n-2$ inside the length $n$ string and also that one string with all bits $0$ except the first $1$.]
Which means $a_n=a_{n-2}+a_{n-1}$. So, $a_n=F_n$ where $F_n$ is the $n$th fibonacci number. So, number of achievable numbers upto 11 bits binary string, $1+a_1+a_2+\cdots+a_{11}=a_{13}=233$.

[Mehrab4226]

How did the idea of using Binary came? (The computer?) If someone tried to see what happens when we use binary he will get that binary forms a quite simple procedure and easy to notice. But the idea of trying with binary is not something I do in every problem. Do you try to use binary in every problem? Why/How did binary come to your mind?
And the solution was great. I loved it.

[Anindya Biswas]

How did the idea of using Binary came? (The computer?) If someone tried to see what happens when we use binary he will get that binary forms a quite simple procedure and easy to notice. But the idea of trying with binary is not something I do in every problem. Do you try to use binary in every problem? Why/How did binary come to your mind?
And the solution was great. I loved it.

Thanks. This idea only works for a few problems. In this particular one, this $4x+1$ might be a little problematic to do again and again. By applying it multiple time, you will get something like $1+4+4^2+\cdots$. Also, after some experimentations, you might discover that $g\left(f(x)\right)=2x$. Then you might realize, doing this calculations in other bases like binary should make things easier since $4x+1$, $2x$ this operations are easy to handle in that case. And I don't know if that computer in the problem was intentional or not, but it didn't help me to come up with the idea of binary.