BdMO Online Forum

মুগ্ধ আর স্নিগ্ধ পরস্পরের সাথে একটা খেলা খেলছে। মুগ্ধর কাছে একটা লাল কম্পিউটার আছে। যদি সেই কম্পিউটার স্ক্রিনে \(x\) সংখ্যাটা দেখা যায়, তাহলে মুগ্ধ হয়:

\(1\). \(x\)-এর সাথে \(1\) যোগ করতে পারে, অথবা
\(2\). \(x\)-কে \(2\) দিয়ে গুণ করে দিতে পারে।

স্নিগ্ধর কাছেও একটা কম্পিউটার আছে কিন্তু সেটা নীল। সেই কম্পিউটারের স্ক্রিনে যদি \(y\) সংখ্যাটা দেখা যায়, তাহলে স্নিগ্ধ হয়:

\(1\). \(y\)-এর সাথে \(1\) যোগ করতে পারে, অথবা
\(2\). \(y\)-কে \(4\) দিয়ে গুণ করে দিতে পারে।

তাদের উভয়ের কম্পিউটার স্ক্রিনেই শুরুতে \(0\) সংখ্যাটা থাকে। কোনো একটা পূর্ণসংখ্যা \(n\)-এর জন্য, মুগ্ধ আর স্নিগ্ধ উভয়েই তাদের নিজের নিজের কম্পিউটারে \(0\) থেকে শুরু করে সর্বনিম্ন সংখ্যক মুভ ব্যবহার করে \(n\)-এ পৌঁছাতে চায়। কিন্তু কিছু কিছু পূর্ণসংখ্যা অপরাজেয় - যেগুলোতে মুগ্ধ আর স্নিগ্ধ সমান সংখ্যক মুভ ব্যবহার করে পৌঁছাবে। \(256\) থেকে \(1024\)-এর মধ্যে কতগুলো অপরাজেয় সংখ্যা আছে?



Mugdho and Snigdho are playing a game against each other.

Mugdho has a red computer. If the computer screen displays the number \(x\), Mugdho can make a move and choose to:
\(1\). Add \(1\) to \(x\).
\(2\). Multiply \(x\) by \(2\).

Snigdho has a blue computer. If his screen displays the number \(y\), Snigdho's moves are:
\(1\). Add \(1\) to \(y\).
\(2\). Multiply \(y\) by \(4\).

They both start with a \(0\) on their screen. Given an integer \(n\), Mugdho and Snigdho are trying to reach \(n\) from \(0\) on their computer in the minimum number of moves. But some integers are unbeatable - Mugdho and Snigdho will reach them in the same number of moves! Find the number of unbeatable integers between \(256\) and \(1024\) (inclusive).

We can run the process backward. In Mugdho's case, we can start with a number and work our way backward to reach $0$ at the minimum moves possible. To get the minimum, our backward process would be like this :
1. We will subtract $1$ until we reach a number which is divisable by $2$
2. We will divide by $2$ when we reach a number which is divisable by $2$
Following the steps, we can reach $0$ with the minimum turns possible. And doing this backward, we can reach the number from $0$.
Snigdho's case will be similar. He would subtract $1$ until he reaches a number which is divisable by $4$ and divide by $4$ when he can. Then work backward.

The indication to use binary system is clearer than that problem in the secondary level. So, let's just jump into that. To demonstrate how Mugdho's and Snigdho's algorithm works, here's an example, Mugdho and Snigdho both have to reach $(100110110)_2$ :
Mugdho's case :
$0_2\mapsto1_2\rightarrow10_2\rightarrow100_2\rightarrow1000_2\mapsto1001_2\rightarrow10010_2\mapsto10011_2\rightarrow100110_2\rightarrow1001100_2\mapsto1001101_2\rightarrow10011010_2\mapsto10011011_2\rightarrow100110110_2$
Observation : We multiplied by $2$ to increase bits and added $1$ to get those $1$s in the binary string.
$\therefore$ Number of moves for Mugdho $=$ (Number of bits) $-1+$ (Number of $1$s) [Notice we subtracted $1$ because the first digit is already there, we didn't have to waste a move for adding that]

Now, Snigdho's case :
For this case, we will write the binary string with groups of $4$s like this :
$(100110110)_2=(01$ $00$ $11$ $01$ $10)_2$ [Notice that we added a zero to the front to complete the pairing, this is essential cause just like Mugdho's case, this pairs of bits will represent how many times we have to add $1$, also note that multiplying by $4$ results in two tailing $0$s]
His process would look like :
$00_2\mapsto01_2\rightarrow01$ $00_2\rightarrow01$ $00$ $00_2\mapsto01$ $00$ $01_2\mapsto01$ $00$ $10_2\mapsto01$ $00$ $11_2\rightarrow01$ $00$ $11$ $00_2\mapsto01$ $00$ $11$ $01_2\rightarrow01$ $00$ $11$ $01$ $00_2\mapsto01$ $00$ $11$ $01$ $01_2\mapsto01$ $00$ $11$ $01$ $10_2$
Observation : Multiplying by $4$ increases $2$ bits. Then we have to add $1$ for zero, one, two or three times to get the neccessary $1$s in the string. To get a $1$ in a even position, it takes $2$ moves, here even position means the position of that bit if we consider the rightmost digit as the first digit, and then counting from right to left. In other words, a bit is in even position if it is the starting bit of a pair of bits, odd position otherwise.
$\therefore$ Number of moves for Snigdho $=$ (Number of pairs) $-1+$(Number of $1$s in the odd position)$+2\times$(Number of bits in the even position) [We subtracted $1$ because the first pair of bits is already there, we have to waste moves for the other pairs]

My writing has already created a mess. To get things even more messier, here's some notations and their definitions :
$M(n)=$ Number of minimum moves required for Mugdho to reach $n$
$S(n)=$ Number of minimum moves required for Snigdho to reach $n$
$b(n)=$ Number of bits in the binary representation of $n$
$d_e(n)=$ Number of $1$s in the even position of the binary representation of $n$
$d_o(n)=$ Number of $1$s in the odd position of the binary representation of $n$
$U_{b(n)}=$ Number of unbeatable numbers of $b(n)$ bits long binary string.

Here's the two equations we got earlier in a little better condition :
$M(n)=b(n)+d_e(n)+d_o(n)-1\dots\dots(1)$
$S(n)=\lceil\frac{b(n)}{2}\rceil+2\cdot d_e(n)+d_o(n)-1\dots\dots(2)$
So, the necessary and sufficient condition for $S(n)=M(n)$ is,
$b(n)+d_e(n)+d_o(n)-1=\lceil\frac{b(n)}{2}\rceil+2\cdot d_e(n)+d_o(n)-1$
$\Leftrightarrow d_e(n)=b(n)-\lceil\frac{b(n)}{2}\rceil$, which is the maximum number of even positions possible in a binary string. That means every even positions must be filled with $1$s.
We can fill the other positions as we wish. One exception is if $b(n)$ is odd, then the first digit is in a odd position, but that bit must be $1$.
So, when $b(n)$ is even, $U_{b(n)}=2^{\frac{b(n)}{2}}$
When $b(n)$ is odd, $U_{b(n)}=2^{\frac{b(n)-1}{2}}$
When $256\leq n<512$, $b(n)=9$
When $512\leq n<1024$, $b(n)=10$
when $n=1024$ it is easy to check that this is not a unbeatable number.
So, the number of unbeatable numbers between $256$ and $1024$ is, $U_9+U_{10}=2^4+2^5=16+32=48$