Problem
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:
- Add $1$ to $x$.
- Multiply $x$ by $2$.
Snigdho has a blue computer. If his screen displays the number $y$, Snigdho's moves are:
- Add $1$ to $y$.
- 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. (BdMO 2020)
My approach
Mugdho's case: We take the numbers in binary to solve the problem. We consider the case when Mugdho tries to reach $0$ from a number $n$. For minimum number of moves, we divide a number by $2$ if it is even and we subtract $1$ from the number if it is odd until we reach $0$. Dividing a number by $2$ removes the last bit of the string.
Now, some observations lead that the number of moves$=$ number of bits$+$number of 1s$-1$.
Snigdho's case: We do the same thing as before. This time we subtract $1$ from a number until we get a number divisible by $4$ and divide a number by $4$ if it is divisible by $4$ to reach $0$. Dividing a number by $4$ removes the last two bits of the string.
But this time, I can't find a closed form of the number of moves as I did in the previous case. I got the number of moves$=$ number of pairs of $0+$ number of $1$s$-1$. But this doesn't work.
I need to complete the solution. And some other ways to solve the problem are also welcome.
You can re-state the formula for Mughdo as (sum of binary digits) + (number of binary digits) - 1.
By the same reasoning, the formula for Snighdo is (sum of base-4 digits) + (number of base-4 digits) - 1.
Now, suppose first that the number of binary digits is even. Then we can split the binary expansion into groups of two, each group corresponding to a base-4 digit: $00\to 0, 01\to 1, 10\to 2, 11\to 3$. Such a group has two binary digits but only one base-4 digit; so to compensate, its base-2 sum must be one less than its base-4 sum. In other words, its base-4 digit must be $2$ or $3$.
And if the number of binary digits is odd, then the first base-4 digit must be $1$; so the sum and number of the base-2 digits, and the sum and number of the base-4 digits, are all equal to 1.
So an integer is unbeatable if and only if all the digits in its base-4 expansion, except possibly the first, are equal to 2 or 3. Now it's easy to count the unbeatable numbers between $256=10000_4$ and $1024=100000_4$. (You get the same answer as in Jitendra Signh's link, but without the mess.)