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?

If we consider only two digit numbers, then the largest set that we can form such that each element differs by 2 digits, has 10 elements.

Without loss of generality we can let this base set be {00,11,22,33,44,55,66,77,88,99}.  This allows us to form a set of 10-digit numbers of the form abcdefghXX such that each differs by two digits.  So there are 10.10^8 = 10^9 elements in this larger set.

The set cannot be greater than this since if we change the last digit, then this number will only differ by one digit from some existing element e.g.  abcdefgh01 differs by one from abcdefgh00 or abcdefgh11 which are in the full set.

The positioning of the base number and their selection of the base set is arbitrary ([01,10,23,32,45,54,67,76,89,98} works as well) but the total size is capped.

Generally if we require d digits to be different in an n-digit number, we get as suspected c(n,d) = 10^(n-d+1) sufficiently different numbers.

 

Posted by goFish on 2005-12-02 07:42:48