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!
Best Answer
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.