0
$\begingroup$

a PIN is a string of four decimal digits, e.g. 2357, 0944 etc.

I am wondering how to find the number of PINs that contain at least one sequence of three consecutive digits $n; n+1; n+2$ (e.g. 2340, 5678 etc).

And the number of PINs that contain at least one sequence of two consecutive digits $n; n+1$ (e.g. 7340, 5671 etc).

It seems that I need to use inclusion and exclusion principle to do this.

$\endgroup$
2
$\begingroup$

You are right that one way to solve this problem is with the principle of inclusion and exclusion.

For the "at least 3 consecutive digits" case, note that there are 8 possible sets of 3 consecutive digits. These digits can be at the right of the pin (like X234) or at the left (234X), where X can be any digit. This gives $8 \cdot 2 \cdot 10 = 160$ pins. However, we have now counted pins with 4 consecutive digits 2 times: for example, 1234 is counted as 123X and X234. Thus we subtract the number of these pins which is 7 to get $153$ pins with at least 3 consecutive digits.

You can extend this method to the second part too. Add all pins with 2 known consecutive digits, subtract some with 3 known consecutive digits, add some with 4 consecutive digits, where "some" is chosen such that each of those categories is counted exactly once.

$\endgroup$
  • $\begingroup$ Thanks so much. The second part seems a bit complicated. By the same method, I get $9*3*10*10=2700$ pins. Then I am not sure what I have over-counted. $\endgroup$ – PropositionX Apr 23 '17 at 2:58
  • $\begingroup$ To start off, how many times have you counted the pin 1235? How many times have you counted the pin 123X for any X? $\endgroup$ – shardulc says Reinstate Monica Apr 23 '17 at 2:59
  • $\begingroup$ For $1235$, this has been counted as $12XX$ and $X23X$. $\endgroup$ – PropositionX Apr 23 '17 at 3:01
  • $\begingroup$ OK. What about a general pin with 3 consecutive digits? $\endgroup$ – shardulc says Reinstate Monica Apr 23 '17 at 3:05
  • $\begingroup$ Is that $8*2$? because I can have $123X,234X,... X123,X234,...$. For each one, I over-counted once. $\endgroup$ – PropositionX Apr 23 '17 at 3:10

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.