[This question is based on one from Reddit]
Consider the set A of 4-digit numbers 0000-9999. We want to construct a set B from the set A such that every item in B differs from every other item in B by at least 2 digits. For example, if 1234 is in B, then 0234, 9234, 1264, etc cannot be in B, but 5634 can be in B.
Specifically:
- What is the size of the largest set B?
- How do we go about generating B from A?
I've hit a dead end trying to find a closed-form solution. A simulation got me up to 950 for the largest size for set B, so I know the largest size is at least 950. Intuition tells me the max is 1000, but I have no idea how to prove that or how to generate a/the set of 1000.
The maximum is indeed $1000$. Let $B$ be the set of numbers whose digit sum is a multiple of $10$. Some examples are $0000,0019,00028,3241$ and $7896$.
There are exactly $1000$ numbers in $B$, because for any three digits $a,b,c$, there is exactly one number in $B$ whose first three digits are $abc$. Furthermore, no two numbers in $B$ can agree in exactly three places, because any three digits of a number in $B$ uniquely determine the fourth digit.