Tessellate S.T.E.M.S. (2019) - Mathematics - School - Set 1 - Objective Problem 5

The answer is $\boxed{10^5}$ , that is, $10^5$ phone numbers can be assigned.

One method for doing so is to use a ‘check digit’, as follows. For each of the $10^5$ $5$ -digit strings $x_1x_2x_3x_4x_5$ , define digit $x_6$ so that $x_6 \equiv \sum_{i=1}^5 x_i \pmod{10}$ and produce the $6$ -digit phone number $x_1x_2x_3x_4x_5x_6$ . Then, for any pair of distinct $6$ -digit strings $x_1x_2x_3x_4x_5x_6$ and $y_1y_2y_3y_4y_5y_6$ constructed in this way, there must be at least one position $j$ with $1 \leq j \leq 5$ such that $a_j \neq b_j$ .

• If there are two such $j$ ’s, these two strings differ at those two places.

• If there is only one such $j$ , then $y_6 - x_6 \equiv (y_1 + y_2 + y_3 + y_4 + y_5) - (x_1 + x_2 + x_3 + x_4 + x_5) \equiv y_j - x_j \not\equiv 0 \pmod{10}$ implying that $y_6 \neq x_6$ . Hence $x_1x_2x_3x_4x_5x_6$ and $y_1y_2y_3y_4y_5y_6$ are differ at the $j$ th and the $6$ th places.

In any case, $x_1x_2x_3x_4x_5x_6$ and $y_1y_2y_3y_4y_5y_6$ must differ in at least two places.

To show that no method can produce a greater number of acceptable phone numbers, observe that among $10^5 + 1$ distinct phone numbers, two would have agree in their first five places, where only $10^5$ distinct $5$ -digit combinations are possible. These two phone numbers would differ in only in the $6$ th place.