parallel_chase wrote:chayanika wrote:A state issues license plate with the following pattern : each plates has three digits (1 through 9). However , each digit must be equal to or greater than the one preceding. (For ex 121 is not permissible combination because the last 1 is less than the digit before it) How many different license plates can the state issue?
1) 210
2) 220
3) 222
4) 242
5) 165
Correct answer is 165
Please explain how to tackle this question
This question involves use of permutations as well as identifying the pattern.
options 1-9
Calculate permutations for only 100's
1*1*9 = 9 ways [place 1 at first place, 1 again second place, we have 9 options equal and greater than 1]
1*1*8 = 8 ways [place 1 at first place, 2 at second place, we have 8 options equal and greater than 2]
With similar reasoning below permutations follow with second place changing in increasing order from 3-9
1*1*7 = 7 ways
1*1*6 = 6 ways
1*1*5 = 5 ways
1*1*4 = 4 ways
1*1*3 = 3 ways
1*1*2 = 2 ways
1*1*1 = 1 ways
9+8+7+6+5+4+3+2+1 = 45 ways
For 200's follow the same as above
1*1*8 = 8 ways [ 2 at first place, 2 again at second place, we have 8 options for third place that are equal and greater than 2]
For 200's we have 8+7+6+5+4+3+2+1 = 36 ways
Now its time to identify the pattern
45 ways
45-9 = 36 ways
36-8 = 28 ways
28-7 = 21 ways
21-6 = 15 ways
15-5 = 10 ways
10-4 = 6 ways
6-3 = 3 ways
3-2 = 1 way
Therefore total possible number of plates are
45+36+28+21+15+10+6+3+1 = 165
This took me more than 5 minutes and I am not able to find a faster way to do this. Whats the source ???
I'm also skeptical about the source, since it seems time consuming.
However, you could have saved a LOT of time if you had started at the top rather than the bottom:
if the first digit is 9, there's only 1 plate: 999
if the first digit is 8, there are 3 plates: 888, 889, 899
if the first digit is 7, there are 6 plates: 777, 778, 779, 788, 789, 799
if the first digit is 6, there are 10 plates: 666, 667, 668, 669, 677, 678, 679, 688, 689, 699
Now if we see the pattern: 1, 3, 6, 10.. increasing by 1 more each time, we project:
1, 3, 6, 10, 15, 21, 28, 36, 45 and them add them up, we get 165 total.
If you saw this approach right away, you could solve in under 2 minutes. I'm sure that there's an "elegant" approach, but I'm not sure that it's any quicker (especially when you factor in the time it takes to find the approach).
