FMM19

Friday Morning Math Problem

Radical Sums

Call a seven-digit phone 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, find the number of different memorable telephone numbers.

Solution

There are 10,000 ways to write the last four digits D4 D5 D6 D7. Among those are 10,000 - 10 = 9,990 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\times 9990+10=19,990$ Alternative solution: Let A denote the set of telephone numbers for which D1 D2 D3 is the same as D4 D5 D6. Let B denote the set of telephone numbers for which D1 D2 D3 coincides with D5 D6 D7. A telephone number belongs to $A\bigcap B$ if and only if D1 = D4 = D5 = D2 = D6 = D3 = D7, so $n(A\bigcap B)=10$. Thus, by the Inclusion Exclusion Principle, ${\begin{aligned}n(A\bigcap B)&=&n(A)+n(B)-n(A\bigcap B)\\&=&10^{3}\times 1\times 10+10^{3}\times 10\times 1-10\\&=&19,990\end{aligned}}$