Let M a positive integer is called “Minos” if in its binary representation, any two consecutive appearance of digit 1 are separated by 2 or more 0. Example 36= 100100 (binary) is “Minos” number, but 37=100101 not.
How many nonnegative integers that can be represented as binary sequence of length 20 (leading zeros allowed) are ‘Minos’?
My tough:
C=# of ceros
N=# of ones
T=# total
*) Two ceros always must be together, when are all 0 . In this case the number 0 is Minos.
*) Now 1 one and 19 ceros 20 different numbers.
*) Now 2 ones and 18 ceros then 20Cn2
In conclusion I’m thinking the solution will be all the sum of all the combination of numbers taken in group of 2.
Note: Regarding my answer, I posted because something doesn’t sound quite right, and I cannot see how can I proceed to calculate the correct answer, and how lead into it. Thanks.
Best Answer
Let $a_n$ be the number of Minos numbers of length $n$. It is not hard to compute $a_1$, $a_2$, and $a_3$.
A Minos number of length $n$ can end in a) $0$ or b) $1$. If $n\ge 2$, the number of Minos numbers that end in $0$ is $a_{n-1}$.
For ending in $1$, where $n\ge 4$, the number obtained by stripping off the $1$ must end in $00$, and the number obtained by stripping off the $00$ must be a Minos number of length $n-3$, and all Minos numbers of length $n$ that end in $1$ can be obtained by appending $001$ to a Minos number of length $n-3$. So there are $a_{n-3}$ Minos numbers of length $n$ that end in $1$.
For $n\ge 4$ we have obtained the recurrence $$a_n=a_{n-1}+a_{n-3}.$$
We can now, a little painfully, use the recurrence to find $a_{20}$.