View source

== Problem ==
Call a <math>7</math>-digit telephone number <math>d_1d_2d_3-d_4d_5d_6d_7</math> ''memorable'' if the prefix [[sequence]] <math>d_1d_2d_3</math> is exactly the same as either of the sequences <math>d_4d_5d_6</math> or <math>d_5d_6d_7</math> (possibly both). Assuming that each <math>d_i</math> can be any of the ten decimal digits <math>0,1,2, \ldots, 9</math>, the number of different memorable telephone numbers is

<math>\mathrm{(A)}\ 19,810
\qquad\mathrm{(B)}\ 19,910
\qquad\mathrm{(C)}\ 19,990
\qquad\mathrm{(D)}\ 20,000
\qquad\mathrm{(E)}\ 20,100</math>
== Solution ==
Let <math>A</math> represent the set of telephone numbers with <math>\overline{d_1d_2d_3} = \overline{d_4d_5d_6}</math> (of which there are <math>1000</math> possibilities for <math>\overline{d_1d_2d_3}</math> and <math>10</math> for <math>d_7</math>), and <math>B</math> those such that <math>\overline{d_1d_2d_3} = \overline{d_5d_6d_7}</math>. Then <math>A \cap B</math> (the telephone numbers that belong to both <math>A</math> and <math>B</math>) is the set of telephone numbers such that <math>d_1 = d_2 = d_3 = d_4 = d_5 = d_6 = d_7</math>, of which there are <math>10</math> possibilities. By the [[Principle of Inclusion-Exclusion]],

<cmath>|A \cup B| = |A| + |B| - |A \cap B| = 1000 \times 10 + 1000 \times 10 - 10 = 19990 \Rightarrow \mathrm{(C)}</cmath>

== See also ==
{{AHSME box|year=1998|num-b=23|num-a=25}}

[[Category:Introductory Combinatorics Problems]]