## BdMO National Secondary 2020 P11

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Secondary 2020 P11
উর্মি কম্পিউটারে একটা গেইম খেলছে। যদি কম্পিউটার স্ক্রিনে $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.
This section is intentionally left blank.

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Contact:

### Re: BdMO National Secondary 2020 P11

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$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm

### Re: BdMO National Secondary 2020 P11

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. The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
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.