BdMO Online Forum

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

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.

Anindya Biswas wrote: ↑

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)\]

$\textbf{Solution}:$