mathfanatic wrote:A certain state issues license plates consisting of six digits (from 0 to 9). The state requires that any two license plates differ in at least two places. (For instance, the numbers 027592 and 020592 cannot both be used.) Determine, with proof, the maximum number of distinct license plates that the state can use.

--Dan

Suppose we have a $ n$ 'digit' number, where each 'digit' can be $ 1$, $ 2$,..., $ m$. Call $ f(m,n)$ the number of the largest set of numbers in this form where each pair of digits differs by at least two digits. Consider the set:\[ \{ (1)(m), (2)(m-1),..., (m-1)(2), (m)(1) \}\] hence $ f(m,2)\ge m$ by example. Take the set that works for $ f(m,n)$, call one of it's elements $ x$. Lets add another digit on the left. We can generate a new set with $ m*f(m,n)$ elements that has $ x1$, $ x2$,...,$ xm$. We repeat this for each of the elements of for the $ f(m,n)$ set. Each of pair these elements have at least two different digits by definition. Hence $ f(m,n+1)\ge m*f(m,n)$. Hence $ f(m,n)\ge m\cdot f(m,n-1)\ge m\cdot (m \cdot f(m,n-2))\ge... \ge m^{n-2}*f(m,2)\ge m^{n-1}$. For sake of contradiction, suppose that $ f(m,n)\ge m^{n-1}+1$. Suppose that $ S$ is such a set. Partition the elements of $ S$ into subsets where the first $ n-1$ digits are equal. Call these sets $ S_i$. There are at most $ m^{n-1}$ of these sets. By the pidgeonhole principle, one of these sets must have two elements. But that means that they have only one different digit since the n-1 digits are equal in each set. Contradiction. Hence $ f(m,n)\le m^{n-1}$. But then $ f(m,n)=m^{n-1}$. We don't need to demonstrate that a corresponding set exists because the set of subsets that have the property is non-empty.

I'd like to share a nice solution. Clearly, the answer is at most $10^5$ because if it were any larger, we can use the pigeonhole principle to show that there will be two numbers that differ in less than 2 digits. I now give a construction of the desired set of $10^5$ numbers. Take the set of $10^5$ distinct 5-digit numbers. Define the 6th digit to be the sum of the first five digits mod 10. This clearly satisfies the given conditions because any two 5-digit numbers who differ in only 1 digit will differ in their 6th digit.

Clearly issuing more than $10^5$ license plates simply means that there exists two license plates with the same digits in the first five places,so that these two license plates differ by atmost one place,contrary two the condition of the problem. Now we show a construction with $10^5$ numbers: We consider the first five places and the last place modulo 10 to the sum of the digits in the first five places.Now if among the first five places two codes differ in two places then everything is fine.Otherwise wlog they differ in the fifith place.Then: last digit of the first number $\equiv a+b+c+d+e \neq a+b+c+d+e' \equiv$ last digit of the last number.So that they differ in two places. Here $a,b,c,d,e$ and $a,b,c,d,e'$ are the digits in the first five places in the two codes. There may also be other constructions,but in my opinion this is the most elegant one.

Obviously, we can have at most 100,000 plates, since if we had any more, there must be some two plates with the same first 5 digits. For a construction for 100,000, take every plate whose sum of digits is a multiple of 10. There are 100,000 of these since the last digit is unique once we choose the first 5 digits. Additionally, this works since two plates that are different in at most one position can have a sum of digits difference of at most 9. Remark: the construction is motivated by: -in a 10x10 square, we can choose the main diagonal so that no two chosen cells are in the same row or column -for a 10x10x10 cube, we can have the 10 layers be cyclic shifts the the 10x10 square earlier, so it still works -for a 10x10x10x10, have the 10 cubes be the cyclic shifts of the previous 10x10x10, and so on when we get to 6 dimensions we will have different tiers of cyclic shifting, but this just amounts to the sum of coordinates being divisible by 10