Bank is planning to produce and grant a special credit card to its loyal costumers. Each of these credit cards has a unique ID-number that has 16 digits and satisfies the following properties:
(i) The first four digits of the ID-numbers is fixed and is equal to 2024.
(ii) For each pair of cards their corresponding ID-numbers must differ in at least two digits.
Prove that the maximal possible number of cards that can be produced is .
Solution
Let the ID-number be , where each is a digit ( to ). By condition (i), is fixed. So, the remaining digits can be chosen.
Let be the set of all possible -digit strings (from to in each position), i.e., .
We are to select a subset such that for any two distinct elements , and differ in at least positions (digits).
We claim that the maximal possible size of is .
Proof:
Let us construct such a set of size .
Let be the set of all -digit numbers whose last digit is . That is, . There are such numbers, since can be arbitrary ( digits), and .
Now, for any two distinct elements , they must differ in at least one of the first digits (since the last digit is always ). But since they are distinct, there is at least one position among to where they differ. However, we need to ensure that they differ in at least digits.
So, instead, let us consider the set of all -digit numbers whose last two digits are . That is, . There are such numbers.
But the problem asks for .
Let us generalize. Consider the set of all -digit numbers where is fixed (say ), and the remaining digits are arbitrary. Then .
For any two distinct elements , they differ in at least one of to . Since is fixed, the only way and can differ is in to . But since they are distinct, there is at least one position where they differ. However, it is possible that they differ in only one digit, which does not satisfy the condition.
Therefore, we need to find the largest possible subset of such that any two elements differ in at least digits.
This is a classical coding theory problem: the largest possible size of a code of length over an alphabet of size with minimal distance .
The answer is given by the following construction:
Let be the set of all -digit numbers with no two the same, and such that for each , at most one element of is at Hamming distance or from .
Let us count the number of -digit numbers at Hamming distance or from a fixed :
- Hamming distance : itself.
- Hamming distance : For each of the positions, there are choices (since each digit can be changed to other digits), so .
So, for each , there are numbers at Hamming distance or from .
If is a code with minimal distance , then the balls of radius around each codeword are disjoint and cover numbers. Since the total number of -digit numbers is , we have:
But the problem claims that is possible.
Let us construct as follows:
Let be the set of all -digit numbers where the sum of the digits is congruent to modulo .
For any two distinct elements , their digit sums are both modulo . If and differ in only one digit, say at position , then the sum of digits of and would differ by a nonzero amount, so their sums modulo would be different, which is a contradiction. Therefore, any two elements of differ in at least digits.
How many such numbers are there? For any choice of the first digits, the last digit is determined modulo to make the sum modulo . So, such numbers.
Therefore, the maximal possible number is .
Thus, the answer is .