Problem:
Call a 7-digit telephone number d1​ d2​ d3​−d4​ d5​ d6​ d7​ memorable if the prefix sequence d1​d2​d3​ is exactly the same as either of the sequences d4​d5​d6​ or d5​d6​d7​ (possibly both). Assuming that each di​ can be any of the ten decimal digits 0,1,2,…9, the number of different memorable telephone numbers is
Answer Choices:
A. 19810
B. 19910
C. 19990
D. 20000
E. 20100
Solution:
There are 10,000 ways to write the last four digits d4​ d5​ d6​ d7​, and among these there are 10000−10=9990 for which not all the digits are the same. For each of these, there are exactly two ways to adjoin the three digits d1​d2​d3​ to obtain a memorable number. There are ten memorable numbers for which the last four digits are the same, for a total of 2⋅9990+10=19990.
OR
Let A denote the set of telephone numbers for which d1​ d2​ d3​ and d4​ d5​ d6​ are identical and B the set for which d1​d2​d3​ is the same as d5​d6​d7​. A number d1​ d2​ d3​−d4​ d5​ d6​ d7​ belongs to A∩B if and only if d1​=d4​=d5​=d2​=d6​=d3​= d7​. Hence, n(A∩B)=10. Thus, by the Inclusion-Exclusion Principle.
n(A∪B)=n(A)+n(B)−n(A∩B)=103⋅1⋅10+103⋅10⋅1−10=19990