# Math Help - Combinatorics

1. ## Combinatorics

How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighbouring 0s?

I know that the last two digits as a number have to be a multiple of 4 so the number is: $\overline{\dots 20}$.

And how can I count the numbers not containing neighbouring 0s?

2. Originally Posted by james_bond
How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighbouring 0s?

I know that the last two digits as a number have to be a multiple of 4 so the number is: $\overline{\dots 20}$.

And how can I count the numbers not containing neighbouring 0s?

I have not gone over it carefully since I have to go now, but here is a guess.

Generalise it for: $\mathop {a_n ...a_3 20}\limits^{\_\_\_\_\_\_\_\_\_\_\_\_}$ show that the number of possibilities is [tex] f_n [/Math] (nth fibonacci number) Try using induction (draw a diagram)

3. Originally Posted by james_bond
How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighboring 0s? I know that the last two digits as a number have to be a multiple of 4 so the number is: $\overline{\dots 20}$.
I assume that 0202020220 will count as such a ten-digit number even though it begins with a zero.
$\sum\limits_{k = 0}^4 {\binom{9-k}{k}}=55$ is the answer.
In the first eight places in the number we can have anywhere from no 0’s(k=0) to at most four 0’s(k=4).
Then there will be 8-k 2’s creating 9-k to place and separate the 0’s.

4. Hello, James!

How many different ten-digit number can be created using only 2s and 0s
which is divisible by 4 and doesn't contain two neighbouring 0s?

I know that the last two digits as a number have to be a multiple of 4
. . so the number ends in: . $\hdots 20$

And how can I count the numbers not containing neighbouring 0s?
I assume that the leading digit cannot be zero.

So we have: . $2\:\_\:\_\:\_\;\_\;\_\;\_\;\_\;2\;0$
. . Hence, we want 7-digit numbers with non-adjacent 0s.

I couldn't find a way to think through this task, so I drew a tree diagram.
. . And here's what I found . . .

. . $\begin{array}{c|c}\text{no. of digits} & \text{no. of ways} \\ \hline
1 & 2 \\ 2 & 3 \\ 3 & 5 \\ 4 & 8 \\ 5 & 13 \\ \vdots & \vdots \end{array}\quad\hdots\quad\text{These are Fibonacci numbers!}$

Hence, there are 34 seven-digit numbers with non-adjacent 0s.

Therefore, the answer is: . ${\bf{\color{blue}34}}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Plato allowed a leading zero, so his result is the next Fibonacci number, 55.