3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think there are $2743$ such numbers of length $20$. My solution is too long. Should I post it? $\endgroup$
    – user98186
    Nov 24, 2015 at 17:14

3 Answers 3

6
$\begingroup$

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}$.

$\endgroup$
4
  • $\begingroup$ One can also solve the recurrence from its characteristic equation, but I'm not sure which is more painful. $\endgroup$ Sep 30, 2015 at 15:44
  • 1
    $\begingroup$ @AustinMohr: Cubics with no obvious solution are quite painful! $\endgroup$ Sep 30, 2015 at 15:51
  • 2
    $\begingroup$ Shouldn't be too hard to find a doubling formula (similar to $F_{2n}=F_n(2F_{n+1}-F_n)$ and $F_{2n+1}=F_{n+1}^2+F_n^2$ for the Fibonacci numbers). Perhaps less painful. @AustinMohr $\endgroup$ Sep 30, 2015 at 16:06
  • $\begingroup$ That is a very nice suggestion. Maybe $20$ is already large enough for binary methods to be more efficient. $\endgroup$ Sep 30, 2015 at 16:23
3
$\begingroup$

Try to set up a recurrence on the length $n$, denote the number of Minos of length $n$ by $M_n$. It is $M_0 = 1$, $M_1 = 2$ ($\{0, 1\}$), $M_2 = 3$ ($\{00, 01, 10\}$)

OK, now consider a Minos of length $n$. If the last digit is $0$, before that came a Minos of length $n - 1$. If the last digit is $1$, it must really end in $001$, before that you have a Minos of length $n - 3$. So:

$$M_{n + 3} = M_n + M_{n + 2}$$

Just churn through the numbers starting with $n = 0$.

$\endgroup$
2
$\begingroup$

Let $m$ be the number of 1's in a Minos number of length 20, so $0\le m\le7$.

If we insert two zeros between each consecutive pairs of 1's,

we have $(20-m)-(2m-2)=22-3m$ zeros left to distribute in the gaps created by the $m$ 1's;

and there are $\dbinom{22-2m}{m}$ ways to do this $\;\;$(for $m\ge2$).

Therefore there are $\displaystyle\sum_{m=0}^7\binom{22-2m}{m}=2745$ Minos numbers of length 20.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .