Numbers with same first and last digits
Probability
Level
3
How many numbers are there that satisfy all these rules?
- The number has 10 digits.
- It only contains 1, 2, or 3. (You don't need to use all.)
- Consecutive digits are different.
- The first and last digits are the same: both 1, both 2, or both 3.
The answer is 510.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Say that f(n) is the function for how many numbers satisfies those rules for n digits. So we want to find f(10).
If a number with n digits ends with a number that is not its first digit, you can add that number at the end and get a number with n+1 digits that satisfies the rules. Like say 132132 starts with 1 and ends with 2 so if we add 1 at the end we get 1321321 which has 1 more digit and is what we want. So we can say that the number of numbers that starts and ends with different numbers and has n digits is the same as the number of numbers that starts and ends with same number and has n+1 digits because again, we can always add that first digit at the end of that number to get a new unique number. You can say that OK but finding that is even harder! Yes, it is, but there's something else we can do. A number can either end with what it started with, or what it didn't start with. So sum of those two will be equal to all numbers. And how many numbers are there with n digits, only has 1, 2 or 3 and consecutive numbers are different? Well first digit can be any of those 3 and other ones all can be the other 2 that are not what was before. So 3 choices for first and 2 for all remaining n-1, if you multiply all that makes 3x2^(n-1).
So the whole thing is:
(Numbers with different start and end with n digits) + (Numbers with same start and end with n digit) = 3x2^(n-1)
First one is the same as the numbers with same start and end with n+1 digits, as we just said, and we named that f(n+1) and second one f(n) at the start! So last but not least:
f(n+1) + f(n) = 3×2^(n-1)
Rearranging:
f(n+1) = 3×2^(n-1) - f(n)
And we know that f(1) is 3 (Because it's just 1, 2 or 3), we can work up to f(10)!
f(2) = 3x2^(1-1) - f(1) = 3 - 3 = 0
f(3) = 6 - 0 = 6
f(4) = 12 - 6 = 6
f(5) = 24 - 6 = 18
f(6) = 48 - 18 = 30
f(7) = 96 - 30 = 66
f(8) = 192 - 66 = 126
f(9) = 384 - 126 = 258
And finally f(10) = 768 - 258 = 510