4
$\begingroup$

Let say any 7-digit sequence, even 0000000 is a valid number. Compute the number of sequences that contain a 5-digit consecutive substring. For example “23456” and “12345”?

Approached it as (where X can be (0-9)) : Which gives me a total as 1800, however the answer is 1700. Can you please point out what I over-counted and share a wise way to approach similar question ?

 0 1 2 3 4 X X 
 1 2 3 4 5 X X
 2 3 4 5 6 X X
 3 4 5 6 7 X X
 4 5 6 7 8 X X
 5 6 7 8 9 X X 

 X 0 1 2 3 4 X  
 X 1 2 3 4 5 X 
 X 2 3 4 5 6 X 
 X 3 4 5 6 7 X 
 X 4 5 6 7 8 X 
 X 5 6 7 8 9 X

 X X 0 1 2 3 4  
 X X 1 2 3 4 5 
 X X 2 3 4 5 6 
 X X 3 4 5 6 7 
 X X 4 5 6 7 8 
 X X 5 6 7 8 9
$\endgroup$
5
  • 3
    $\begingroup$ What have you overcounted? How about the string 0 1 2 3 4 5 6? You counted it once when you noticed it had 0 1 2 3 4 in it, you counted it again when you noticed it had 1 2 3 4 5 in it, and again when you noticed it had 2 3 4 5 6 in it. Similarly so for any other string with more than 5 consecutive digits in a row. $\endgroup$
    – JMoravitz
    Sep 27, 2018 at 5:53
  • 1
    $\begingroup$ This problem is a good setting to apply the Inclusion-Exclusion principle. $\endgroup$
    – Carl
    Sep 27, 2018 at 5:58
  • $\begingroup$ The standard way to correct the overcounting is called the inclusion-exclusion principle. $\endgroup$
    – Arthur
    Sep 27, 2018 at 6:01
  • $\begingroup$ Can you please @Carl or Arthur show me how you would use inclusion exclusion principle ? $\endgroup$
    – user487078
    Sep 27, 2018 at 6:07
  • $\begingroup$ the question should be more defined(wording is not precise) as Compute the number of sequence that contain only a 5-digit consecutive substring or Compute the number of sequence that contain at least a 5-digit consecutive substring. here first one would restrict a 6 or 7 digit substring while the second question would allow those $\endgroup$
    – Awakened
    Sep 27, 2018 at 6:20

2 Answers 2

1
$\begingroup$

Yes, you are overcounting the number of such strings: for example $0 1 2 3 4 5 6$ is counted three times: as a member of $0 1 2 3 4 X X$, of $X 1 2 3 4 5 X$, and of $X X 2 3 4 5 6$.

As explained by the comments the right tool to use is the inclusion-exclusion principle.

Hint. Let $S(01234)$ be the set of 7-digit sequences which contain a copy of the string $01234$ then, from your scheme, $$|S(01234)|=3\cdot 10\cdot 10=300.$$

By the inclusion-exclusion principle, the number of 7-digit sequences such that contain at least a 5-digit consecutive substring in increasing order is $$\begin{align}&|S(01234)|+|S(12345)|+\dots+|S(56789)|\\&- |S(012345)|-|S(123456)|-\dots-|S(456789)|\end{align}.$$ P.S. In order to apply the inclusion-exclusion principle you should consider the intersections of the sets $S(\cdot)$. Note that $$S(01234)\cap S(12345)=S(012345),\\ S(01234)\cap S(23456)=S(0123456),\\ S(01234)\cap S(34567)=\emptyset,\\ S(01234)\cap S(12345)\cap S(23456)=S(0123456) .$$

$\endgroup$
1
  • $\begingroup$ @StackExangeLearner Is it clear now how to use PIE? $\endgroup$
    – Robert Z
    Sep 28, 2018 at 12:47
0
$\begingroup$

You are counting some strings twice.

For example, $$xx56789$$ and $$x45678x$$ both results in $$3456789$$

$\endgroup$

You must log in to answer this question.