Unforgettable Mathematical Problems: Episode 1

I am planning to start a series of unforgettable mathematical problems that I have encountered in my life.

First of all, what makes a mathematical problem unforgettable? This of course is a subjective question. Usually, it is a combination of personal factors and elegance of the problem itself. This is the first of of these problems.

The problem under discussion is Problem 1 from the 1990 United States of Mathematical Olympiad. One of my classmates who wrote the contest with me got this problem during the contest. He explained his truly elegant solution to me right afterwards. Although this was almost 34 years ago at the time I am writing this piece, the solution is still fresh in my mind as though he only told me yesterday. (How is that for the timelessness of mathematics?) His solution is so elegant that I even wonder if the creator of the problem thought of this. I distinctly remember him saying that it is related to the so-called check-digit in the library system. Anyway, here is the problem and his beautiful solution (paraphrased in my words):

Problem: What is the maximum number of elements in a subset of 6-digit positive integers such that for any two such integers, they differ by at least two digits? (For clarity, 135566 and 134768 is one such pair since they differ in the thousands, hundreds and ones digit. However, 123456 and 123556 is not one such pair since they differ in only the hundreds digit.)

Solution: Consider the 90000 5-digit numbers from 10000 to 99999. For each such number, we extend it to a 6-digit number by adding a so-called check-digit at the end. Specifically if the number has digits $a, b, c, d, e$ , define the check-digit $f\equiv a+b+c+d+e \pmod{10}$ . For example, for the 5-digit number 10000, its check-digit is 1 so we form the number 100001. Notice that all these 6-digit numbers are different because for any two of them, they differ in at least one place among its five leftmost digits. I claim that these 90000 numbers have the required property.

Indeed, pick any two of them. We are done if they differ by at least two places among its five leftmost digits. Now, they cannot have the same five leftmost digits by construction, so we are left with the case that they differ by exactly one place. But then, the check-digits of these two numbers will be different. In fact, suppose the first number has digits $abcdef$ and the second number has digits $a'b'c'd'e'f'$ . Without loss of generality, if $a\neq a'$ then $x=x'$ for $x=b,c,d,e$ so that $f-f'\equiv a-a'\not\equiv 0 \pmod{10}$ . Thus, the resulting 6-digit numbers differ by two places.

Finally, there cannot be any subsets with the required property with more than 90000 numbers. Indeed, there are only 90000 possibilities for the first five digits. Thus, if there are at least 90001 distinct 6-digit numbers, at least two of them, by The Pigeonhole Principle, will have the same set of 5 leftmost identical digits so they differ by one digit only. We conclude that the maximum possible number of elements in a subset with the required property is 90000.