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 re: 3+ digits? by goFish)

You're proving that you cannot add more numbers to the existing set, but how do you know that you can't "trade," say, 10 of the numbers already in the set for 11 numbers not in the set?

As a counterexample, consider this set using 3-digit binary numbers: {000, 111}
I cannot add any more elements to this set such that all elements are more than 1 digit away.  And yet, I can think of a 4-element set that satisfies the requirements:
{000, 011, 101, 110}

I'm not sure whether or not it would be difficult to fix your proof.

Posted by Tristan on 2006-02-26 02:02:53