How many ten-digit numbers are there in which every digit is 2 or 3, and no two 3s are adjacent?

Question

How many ten-digit numbers are there in which every digit is 2 or 3, and no two 3s are adjacent?

Taken from the 2008 IMC https://chiuchang.org/wp-content/uploads/sites/2/2018/02/2008-IWYMIC-Individual.x17381.pdf

my attempt

The number of ten digit numbers in which the digits are either 2 or 3 is $2^{10}$ and the numbers of ten digit numbers where there is no pair of adjacent numbers that are the same is $2$ E.g($2323232323$ & $3232323232$) and we know that the number of ten digit numbers consisting of pairs of adjacent $2$s and adjacent $3$s is the same due to symmetry therefore the answer would be $\frac{2^{10}-2}{2}=511$ however this doesn't taken into account the possibilities of having adjacent pairs of $3$s and $2$s in the same number.

Answer 1

Suppose you have r number of 3 in a line. Now we know 3 can't be adjacent so I have to put at least 1 in between them. For example-r=3 |-|-|(| denotes 3 and - denotes 2). Now we have x=10-(r+r-1) 2's remaining. Now we can put these 2's in r+1 slots(in the example we can put in 4 slots slot1|slot2|slot3|slot4). Now this becomes a standard problem Stars and bars of x1+x2+x3+..xl=p (where l denotes the number of slots and where every xi can be 0 and p denotes number of 2 we want to distribute which is x in our case). Number of solution of above equation is given by:

$\binom {p+l-1}{l-1}$

here p=10-(r+r-1) and l=r+1(slots) putting these value in above formula we get:

$\binom {11-r}{r}$

Now you can vary r from 0-10 and just add them you will get 144 as the answer. Here you can see you do not need to vary from 6 -10 because when we place 6 or more number we don't have enough 2's to put in between them so they will contribute 0.

Answer 2

Suppose you have $k$ $3$s and it does not end with a $3$.

That the same thing as saying you have $k$ characters $32$ and $10-k-k=10-2k$ twos. So of the $10-2k + k=10-k$ characters you must choose $k$ spaces for the $k$ $32$ characters. There ${10-k \choose k}$ ways to do that.

Now suppose you have $k$ $3$s and it does end with a $3$.

If we just ignore the last place and put the $3$ in it, that is the same thing as saying you have $k-1$ characters $32$ to place and $10-k-(k-1)=11-2k$ $2$s to place. There are ${10-k\choose k-1}$ ways to do that.

So there are ${10-k \choose k}+ {10-k\choose k-1}$ ways to place $k$ threes.

Now we can have at most $5$ threes. (Any more and we won't have enough $2$s to go between all $3$s.)

So there are

$\sum_{k=0}^5 {10-k \choose k}+ {10-k\choose k-1}$ ways. (Assume ${10\choose -1} = 0$.... after all.... this would be the number of ways to choose $0$ threes and have a $3$ at the end which isn't possible.)

So $({10\choose 0}) + ({9\choose 1}+ {9\choose 0}) +({8\choose 2}+{8\choose 1}) + ({7\choose 3}+{7\choose 2}) + ({6\choose 4}+{6\choose3}) + ({5\choose 5} + {5\choose 4})=$

$1 + (9+1) + (\frac {8*7}2 + 8) + (\frac {7*6*5}6 -\frac {7*6}2) + (\frac {6*5*4*3}{24}+\frac{6*5*4}6) + (1 +5)=$

$1 + 10 +(28+8) + (35+21) + (15+20) + 6=$

$11+36+56+35+5=144$