Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1990 USAMO Problems/Problem 1

Revision as of 14:56, 21 October 2007 by Temperal (talk | contribs) (→‎See also: first question)

Problem

A license plate has six digits from 0 to 9 and may have leading zeros. If two plates must always differ in at least two places, what is the largest number of plates that is possible?

Solution

We show by induction that we can find a set of $10^{n-1}$ plates for $n > 1$ digits. It is true for $n = 2$: take the plates $00, 11, 22, ... , 99$. Suppose it is true for $n$. If d is a digit from $0$ to $9$ and $s$ is a plate of $n$ digits, let $[d, s]$ be the plate of $n+1$ digits which has a as its first digit, and the remaining digits the same as those of $s$, except that the last digit is that for $s$ plus $d$ (reduced $\pmod {10}$ if necessary). Let $S$ be a set of plates for $n$ digits. We claim that the set $S' = { [d, s] : d = 0, 1, ...$ (Error compiling LaTeX. Unknown error_msg) or $9$ and $s$ belongs to $S$} is a set of plates for $n+1$ digits. It obviously has $10$ times as many members as $S$, so this claim is sufficient to establish the induction.

We have to show that $[a, s]$ and $[b, t]$ differ in at least two places. If $a = b$, then $s \ne t$, so s and t differ in at least two places. The same change is made to their last digits, so $[a, s]$ and $[a, t]$ differ in at least two places. If $a ≠ b$ (Error compiling LaTeX. Unknown error_msg) and $s = t$, then $[a, s]$ and $[b, s]$ differ in both their first and last places. If $a \ne b$ and $s \ne t$, then $s$ and $t$ differ in at least two places and so the modified s and t, differ in at least one place. But $[a, s]$ and $[b, t]$ also differ in the first place, so they differ in at least two places.

So we have established that the largest number is at least $10^{n-1}$ for $n$ digits.

But any two plates which differ only in the last digit cannot both be chosen. So at most $\frac{1}{10 }$ of the $10^n$ possible plates can be chosen. That shows that $10^{n-1}$ is best possible.

See also

First question USAMO (Problems • question Resources)
Preceded by
[[First question USAMO Problems/Problem {{{num-b}}}|Problem {{{num-b}}}]] 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_1&oldid=18559"