BdMO National 2021 Higher Secondary Problem 7

Discussion on Bangladesh Mathematical Olympiad (BdMO) National

Did you solve it on the contest?

Yes
0
No votes
No
3
60%
No, but I solved it afterwards
2
40%
 
Total votes: 5

User avatar
Anindya Biswas
Posts: 196
Joined: Fri Oct 02, 2020 8:51 pm
Location: Magura, Bangladesh
Contact:

BdMO National 2021 Higher Secondary Problem 7

Unread post by Anindya Biswas » Sat Apr 10, 2021 4:54 pm

একটা বাইনারি স্ট্রিং হলো এমন একটা শব্দ যার মধ্যে খালি \(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

User avatar
Anindya Biswas
Posts: 196
Joined: Fri Oct 02, 2020 8:51 pm
Location: Magura, Bangladesh
Contact:

Re: Solution :

Unread post by Anindya Biswas » Sat Apr 10, 2021 8:25 pm

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 already mentioned,
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}\]
There might be mistakes, if you spot any, feel free to acknowledge me.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply