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

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.

• This is the same as this question
– lulu
Sep 24 '19 at 18:45
• And similar to this, more recent, one. Sep 25 '19 at 5:47

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.

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