Waste less time on Facebook — follow Brilliant.

I need help

Given a set \(\{1;2;3;4;5\}\), find the number of 5 digits numbers that none of its consecutive digits are equal to each other,. If possible, find the sum of them

Note by Gurīdo Cuong
2 weeks, 4 days ago

No vote yet
1 vote


Sort by:

Top Newest

Assuming that the given set is the set of digits we can use (with replacement) to form the 5-digit numbers, the number of such 5-digit numbers with no two consecutive digits equal to each other is equal to \(5\times 4^4=1280\). The combinatorial argument here is constructive: We can select the first digit in 5 ways, then the second digit in 4 ways (excluding the first digit), the third digit in 4 ways (excluding the second digit) and so on till the 5th digit. By the rule of product, there are \(1280\) such numbers.

Now, to find the sum of all such numbers, note that every digit appears exactly \(4^4=256\) times at each digit-place among all such numbers. This can be proved easily using the argument used above. If we fix a digit at a digit-place, its adjacent digits can be chosen in \(4\) ways and their adjacent digits can also be chosen in \(4\) ways since we can't have adjacent digits equal to each other. Repeating this argument shows that for each fixed digit at a fixed digit place, there are exactly \(256\) numbers having the said digit at the said digit-place.

Hence, by the rule of product, the sum is given by, \[256(1+2+3+4+5)(10^4+10^3+10^2+10+1)=42666240\]

To generalize this to some extent, if \(S\) be the set of digits that can be used to make \(n\)-digit numbers with no two consecutive digits equal to each other, then,

  • If \(0\notin S\), there are \(|S|\times (|S|-1)^{n-1}\) such numbers and their sum is given by, \[(|S|-1)^{n-1}\left(\sum_{k\in S}k\right)\left(\sum\limits_{k=0}^{n-1}10^k\right)=\frac{(|S|-1)^{n-1}(10^n-1)\left(\sum\limits_{k\in S}k\right)}9\\~\\\]

  • If \(0\in S\), then there are \((|S|-1)^n\) such numbers. I'm pretty sure that there's a closed form for their sum, but it gets a bit complicated for me. I'm still working on it. I'll edit this comment when I get the closed form.

Prasun Biswas · 2 weeks, 1 day ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...