## Did you solve it on the contest?

Yes
0
No
3
60%
No, but I solved it afterwards
2
40%

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

### BdMO National 2021 Higher Secondary Problem 7

একটা বাইনারি স্ট্রিং হলো এমন একটা শব্দ যার মধ্যে খালি $$0$$ আর $$1$$ আছে। কোনো বাইনারি স্ট্রিংয়ে একটা $$1$$-রান হলো এমন একটা সাবস্ট্রিং যেটাতে খালি $$1$$ আছে এবং যেটাকে আর ডানে বা বামে বড় করা যায় না। কোনো একটা ধনাত্মক পূর্ণসংখ্যা $$n$$-এর জন্য $$B(n)$$ হলো $$n$$-কে বাইনারিতে লিখলে এতে যতগুলো $$1$$-রান থাকে, সেই সংখ্যাটা। উদাহরণস্বরূপ, $$B(107)=3$$ কারণ $$107$$-কে বাইনারিতে লিখলে হয় $$1101011$$ এবং এটাতে ঠিক তিনটা $$1$$-রান আছে। নিচের রাশিটার মান কত?
$B(1)+B(2)+B(3)+\cdots+B(255)$

A binary string is a word containing only $0$s and $1$s. In a binary string, a $\text{1-run}$ is a non-extendable substring containing only $1$s. Given a positive number $n$, Let $B(n)$ be the number of $\text{1-runs}$ in the binary representation of $n$. For example, $B(107)=3$ since $107$ in binary is $1101011$ which has exactly three $\text{1-runs}$. What is the following expression equal to? $B(1)+B(2)+B(3)+\dots+B(511)$
Last edited by Anindya Biswas on Sun Apr 11, 2021 10:32 am, edited 1 time in total.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

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

### Re: Solution :

First thing you will notice is that $511=2^9-1$, which is the largest number with $9$ bit long binary string. For this particular problem, we will consider every integer number from $0$ to $2^9-1$ as a $9$-bit long binary string. For example, $2_{10}=10_2=00000010_2$, which is now a $9$ bit long binary string.
Notice that considering every non negative integer less that or equal to $511$ as a $9$ bit long binary string neither change the number of $\text{1-runs}$ nor their lengths.
Let's now define similarly the $\text{0-runs}$. In a binary string of $9$ bits length, a $\text{0-run}$ is a non-extendable substring that contains only $0$s. Let $C(n)$ be the number of $\text{0-runs}$ in the binary representation of $n$ where $n$ is a nonnegative integer, $n\leq2^9-1$, and the binary representation of $n$ is considered to have a length of $9$ bits.

Let's consider another topic, the $\text{0-runs}$ and $\text{1-runs}$ partition the binary representation in $B(n)+C(n)$ parts. As always, here's an example : $111$-$00$-$11$-$00$ is partitioned into $4$ parts separated by hyphens where each part is either a $\text{0-run}$ or a $\text{1-run}$. Let's call this parts "$\text{island}$".

We also observe that a $9$-bit long binary string has at least one $\text{island}$ and no more than $9\text{ islands}$.
$\therefore 1\leq B(n)+C(n)\leq9$.

There's a well known theorem in combinatorics named Stars and Bars theorem that says a positive number $n$ can be written as a sum of $k$ positive integers in $n-1\choose k-1$ ways.
That means the $9$-bit long binary string can be partitioned into $k$ islands in $8\choose k-1$ different ways.
Here, each number corresponds to a partition. If $n$ corresponds to a partition $P$, then $2^9-1-n$ also corresponds to that partition $P$. Since the binary string associated with $2^9-1-n$ can be found just by flipping every bit of binary representation of $n$. Every number other than $n$ and $2^9-1-n$ corresponds to different partitions.
Summarizing, the equation $B(n)+C(n)=k$ has $2\cdot{8\choose k-1}$ solution. That means there are $2\cdot{8\choose k-1}$ nonnegative integers $n, n\leq2^9-1$ such that $B(n)+C(n)=k$.
Therefore we get : $\sum_{i=0}^{2^9-1} B(i)+C(i)=\sum_{k=1}^{9} 2\cdot{8\choose k-1}\cdot k$
We can get the binary representation of $2^9-1-n$ by flipping every bit of binary representation of $n$.
That means, $B(n)=C(2^9-1-n)$
So, $\sum_{i=0}^{2^9-1} B(i)=\sum_{i=0}^{2^9-1} C(i)$
$\therefore \boxed{\sum_{i=0}^{2^9-1} B(i)=\sum_{k=1}^{9} {8\choose k-1}\cdot k=1280}$