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?

I haven't solved this one myself, beyond the first question, so I have to wait for someone to solve the rest of it before I can post an official solution.

Finding 10^9 codes that differ by 2 digits each is relatively easy.  However having all codes abcdefghXX doesn't work, because, just as Charlie pointed out, 1234567899 differs from 0234567899 by only one digit.  Leming has already fixed his solution so that it still has 10^9 codes, and now works properly.  Nobody's posted a proof of the maximum, but I didn't really ask for a proof anyway.

Finding as many codes as possible that differ by 3 digits is harder.  Several comments have proposed that there are 10^8 codes, but I'm not so sure.  I've tried thinking of sets of 10^8, but each time I find a counterexample.

For example, I proposed abcdefghXX where X is equal to the sum of a through h mod 10.
Counterexample:
1000000011
0100000011
2 digits differ

Prove me wrong.

Posted by Tristan on 2006-02-02 19:22:51