2024 DMC Mock 10 Problems/Problem 19

Problem

The city of Dallas is issuing new $6$ -digit license plates. To make keeping track of different license places easier, each license plate much differ from every other license plate by at least $2$ digits. For example, the license plates $012345$ and $012344$ may not both be issued, while the license plates $012345$ and $012354$ may. What is the maximum number of license plates that can be issued?

$\textbf{(A)}\ 10,000\qquad\textbf{(B)}\ 20,000\qquad\textbf{(C)}\ 50,000\qquad\textbf{(D)}\ 100,000\qquad\textbf{(E)}\ 500,000$

Remark: This problem is identical to the first problem of the 1990 USAMO.

Solution

Consider license plates of $n$ digits, for some fixed $n$ , issued with the same criteria.

We first note that by the pigeonhole principle, we may have at most $10^{n-1}$ distinct plates. Indeed, if we have more, then there must be two plates which agree on the first $n-1$ digits; these plates thus differ only on one digit, the last one.

We now show that it is possible to issue $10^{n-1}$ distinct license plates which satisfy the problem's criteria. Indeed, we issue plates with all $10^{n-1}$ possible combinations for the first $n-1$ digit, and for each plate, we let the last digit be the sum of the preceding digits taken mod 10. This way, if two plates agree on the first $n-1$ digits, they agree on the last digit and are thus the same plate, and if two plates differ in only one of the first $n-1$ digits, they must differ as well in the last digit.

It then follows that $10^{n-1}$ is the greatest number of license plates the state can issue. For $n=6$ , as in the problem, this number is $10^5$ , so the answer is $\boxed{\textbf{(D)}\ 100,000}$ .

Page

Toolbox

Search

2024 DMC Mock 10 Problems/Problem 19

Problem

Solution