Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I got the following question:

How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried solving it logically. I would like to know if my solution is correct, and if possible, how to solve it using the inclusion-exclusion principle.

Thanks!

So I said lets first find the numbers that do include the sequence 12, and divided it into cases:

Between 1 and 99: $1\cdot 1=1$

Between 100 and 999: $1\cdot 1 \cdot 10$ + $9\cdot 1 \cdot 1=19$

Between 1000 and 9999: $1 \cdot 1 \cdot 10 \cdot 10 + 2\cdot 9 \cdot 10 \cdot 1 \cdot 1 = 280$

Between 10000 and 99999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10 + 3\cdot 9 \cdot 10 \cdot 10\cdot 1\cdot 1=3700$

Between 100000 and 999999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10\cdot 10 + 4\cdot 9 \cdot 10 \cdot 10\cdot 10\cdot 1\cdot 1=46000$

Between 1000000 and 9999999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10\cdot 10\cdot 10 + 5\cdot 9 \cdot 10 \cdot 10\cdot 10\cdot 10 \cdot 1\cdot 1=550000$

So the total of numbers that don't include the number 12 is: 10000000-550000-46000-3700-280-19=9400001

I don't havea final answer so I don't know if that correct. Obviousy this solution lacks elegance, so I would like to know how solve this problem using the inclusion-exclusion principle.

Thank in advance!

share|improve this question
    
Not sure if I know how to solve it efficiently or completely correctly, but as advice, take the between 1000-9999 range. I see what you did there: 1-2-X-X + X-1-2-X + X-X-1-2 = 1*1*10*10 + 9*1*1*10 + 9*10*1*1 = 280. But what if you had a number like 1212? That number overlaps in the first case and the third case, and you can only count it once, so that actually leaves you with 280-1 = 279, I hope that helps. –  mathguy May 11 '13 at 15:29
    
Yes I see now. Thank you! –  ohad May 11 '13 at 15:37
    
+1 for a well posed question and for showing your work –  JavaMan May 11 '13 at 16:40
add comment

3 Answers

up vote 2 down vote accepted

So you have at most a 7-digit number (since 10,000,000 isn't a possibility): X-X-X-X-X-X-X, and the 12 can be in 6 different positions, so you have 1-2-X-X-X-X-X, X-1-2-X....,X-X-X-X-X-1-2. That is a total of $6*10^5 = 600,000$ different numbers. Now the hard part like I said above is finding the overlaps.

Suppose 12 were to appear twice, that means that we have 3 open spaces otherwise. How many ways can we reorder the two 12's and the extra 3 spots? That would be ${5\choose2} = 10$. Since the open spots can be $10^3$ different numbers, we end up with $10*10^3 =10,000$ overlaps.

Suppose 12 were to appear three times, that means we have 1 open space otherwise. How many ways can we reorder the three 12's and the extra spot? ${4\choose1} = 4$. Since the open spots can be 10 different numbers, we end up with $4*10 = 40$ overlaps.

However, if 12 were to appear three times, that means 12 also appears 2 times, and so instead of have $10,000$ overlaps (from the first overlap case), we actually have $10,000 - 40 = 9960$ total overlaps.

With $10,000,000$ different numbers, we end up with (total numbers - total overlaps) = $10,000,000 - (600,000-9960) = 9,409,960$ which I verified with Java.

share|improve this answer
    
I see. Thank you! Very nice solution. –  ohad May 11 '13 at 16:03
    
Regarding the number of different numbers that include 12. –  ohad May 11 '13 at 16:05
    
@mathguy good one. –  Uma kant May 11 '13 at 16:08
add comment

All right you are at the first step of the inclusion-exclusion principle. You have just counted those numbers in which 12 appears at least once but in the process have overcounted. Your solution counts $1212$ twice, $121212$ thrice and so on.

By inclusion-exclusion principle, No. of numbers w/o $12$ = Total no. of numbers - No. of numbers with $1$2 at least once + No. of numbers with $12$ twice - No. of numbers with $12$ thrice + No. of numbers with $12$ four times and so on.

Total no: $10,000,000$

  • $12$ at least once: $6*10^5$
  • $12$ at least twice: $(4+3+2+1)*10^3$
  • $12$ at least thrice: $((2+1)+(1))*10^1$
  • $12$ four times and so on $=0$
  • so ans= $10000000-600000+10000-40=9409960$
share|improve this answer
    
Welcome to MSE! It really helps to format questions/answers using MathJax (see FAQ). Regards –  Amzoti May 11 '13 at 16:36
add comment

Keep track of the amount of $n$-digit numbers ending in $1$ and not ending in $1$, starting with $n=1$

$$ v_1 = \begin{pmatrix} 1 \\ 8 \end{pmatrix} $$

so $1+8 = 9$ numbers in total. The vector for $(n+1)$-digit numbers ending in $1$ and not ending in $1$ that do not contain the sequence "$12$" can be obtained by a recursion:

$$ v_{n+1} = \begin{pmatrix} 1 & 1 \\ 8 & 9 \end{pmatrix} v_n. $$

If $M$ is the matrix in the recursion above then there are $$ \begin{pmatrix} 1 & 1 \end{pmatrix}(M^{n-1} + M^{n-2} + \dotsc + 1) \begin{pmatrix} 1 \\ 8 \end{pmatrix} $$ numbers of at most $n$ digits that do not contain the sequence "$12$". For $n=7$ this becomes

$$ \begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix}96031 & 106821 \\ 854568 & 950599 \end{pmatrix} \begin{pmatrix} 1 \\ 8 \end{pmatrix} = 9409959 $$ and including the number $10^7$ the final answer is $9409960$. Based on the above one can find a simpler linear recursion for the amount $a_n$ of numbers of at most $n$ digits that do not contain the sequence "$12$", namely

$$a_0 = 0, a_1=9 \textrm{ and } a_{n+2} = 10 a_{n+1} - a_n + 8.$$

This produces the sequence

$$0, 9, 98, 979, 9700, 96029, 950598, 9409959, 93149000, 922080049, \dotsc$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.