A certain company gives each of its clients a 10 digit number as a sort of identification code. As a precaution, any pair of used codes should differ by at least two digits so no one accidentally gives someone else's code.

How many clients can they have before adding digits? Give an example of a set of codes they might use. What if each pair of codes must differ by at least 3 digits? 4? More?

(In reply to Spoiler by Leming)

The way this scheme would work, I assume is like this as a partial list of numbers:

0123456780
1123456781
2123456782
3123456783
4123456784
5123456785
6123456786
7123456787
8123456788
9123456789

but would also include

0123456790
1123456791
2123456792
3123456793
4123456794
5123456795
6123456796
7123456797
8123456798
9123456799

but each number in the latter set differs by only one digit from the corresponding number in the first set.

Per e.g.'s comment, a check digit would provide the 2-digit differences asked for in the first part.  One way of thinking about it would be to take all 9-digit combinations, then append an extra digit at the end so as to make the total of all the 10 digits congruent to 0 mod 10. You can't make a single-digit change to any given number in this scheme and still have a valid number.

But is there a proof that there is not another scheme, that would allow for more than 10^9 numbers?

Posted by Charlie on 2005-11-29 14:11:02