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.


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.