0

Suppose I have a 6 digit lock that accepts 0-9 as inputs for the 6 slots.

And I was told that the numbers in order from left to right are never less than the number to their left. so 0,0,0,0,0,0 would be valid but 0,1,2,3,2,9 would not.

I tried to brute force it by looking for a pattern in increasing the number of slots on the lock. If it allowed a single digit, 10 passwords. if it allowed 2 digits, 55 passwords (I think)

10 that start with 0,

9 that start with 1,

8 that start with 2,

ect.

10+9+8+...+3+2+1=55

3 gets a lot bigger, 100 that start with 0, then 9 that start with "1,1" 8 that start with "1,2" but from there I get lost with my counting and its going to be a huge nightmare when I get up to 6.

Please tell me there is a better way! Thank you.

Wombles
  • 131
  • The two examples of valid/invalid patterns seem to be switched.... – Greg Martin Mar 15 '21 at 06:46
  • @GregMartin Im not sure they are? the sequence has to be non-decreasing, so 0,0,0,0,0,0 should be valid since each number is not less that the number it follows. – Wombles Mar 15 '21 at 06:52

1 Answers1

1

This is a "stars and bars" problem. If you know how many examples of each digit appear in your number, the non-decreasing condition forces a unique solution. So you need to know how many solutions there are to:

$$\sum_{k=0}^9 x_k=n,$$

where $x_k$ is the number of times the digit $k$ appears in your number, and $n$ is the length of your number. That number is $\binom{n+9}{9}$.

Robert Shore
  • 23,332