Maths Olympiad Prep

Library / /36 of 36

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it Saudi Arabia

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 101110^{11}.

Solution

Let the ID-number be d1d2d16d_1d_2\ldots d_{16}, where each did_i is a digit (00 to 99). By condition (i), d1d2d3d4=2024d_1d_2d_3d_4 = 2024 is fixed. So, the remaining 1212 digits d5,d6,,d16d_5, d_6, \ldots, d_{16} can be chosen.

Let SS be the set of all possible 1212-digit strings (from 00 to 99 in each position), i.e., S=1012|S| = 10^{12}.

We are to select a subset ASA \subset S such that for any two distinct elements x,yAx, y \in A, xx and yy differ in at least 22 positions (digits).

We claim that the maximal possible size of AA is 101110^{11}.

Proof:

Let us construct such a set AA of size 101110^{11}.

Let AA be the set of all 1212-digit numbers whose last digit is 00. That is, d16=0d_{16} = 0. There are 101110^{11} such numbers, since d5,d6,,d15d_5, d_6, \ldots, d_{15} can be arbitrary (1111 digits), and d16=0d_{16} = 0.

Now, for any two distinct elements x,yAx, y \in A, they must differ in at least one of the first 1111 digits (since the last digit is always 00). But since they are distinct, there is at least one position among d5d_5 to d15d_{15} where they differ. However, we need to ensure that they differ in at least 22 digits.

So, instead, let us consider the set AA of all 1212-digit numbers whose last two digits are 0000. That is, d15=d16=0d_{15} = d_{16} = 0. There are 101010^{10} such numbers.

But the problem asks for 101110^{11}.

Let us generalize. Consider the set AA of all 1212-digit numbers where d5d_5 is fixed (say 00), and the remaining 1111 digits are arbitrary. Then A=1011|A| = 10^{11}.

For any two distinct elements x,yAx, y \in A, they differ in at least one of d6d_6 to d16d_{16}. Since d5d_5 is fixed, the only way xx and yy can differ is in d6d_6 to d16d_{16}. 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 SS such that any two elements differ in at least 22 digits.

This is a classical coding theory problem: the largest possible size of a code of length 1212 over an alphabet of size 1010 with minimal distance 22.

The answer is given by the following construction:

Let AA be the set of all 1212-digit numbers with no two the same, and such that for each xSx \in S, at most one element of AA is at Hamming distance 00 or 11 from xx.

Let us count the number of 1212-digit numbers at Hamming distance 00 or 11 from a fixed xx:
- Hamming distance 00: xx itself.
- Hamming distance 11: For each of the 1212 positions, there are 99 choices (since each digit can be changed to 99 other digits), so 12×9=10812 \times 9 = 108.

So, for each xx, there are 1+108=1091 + 108 = 109 numbers at Hamming distance 00 or 11 from xx.

If AA is a code with minimal distance 22, then the balls of radius 11 around each codeword are disjoint and cover A×109|A| \times 109 numbers. Since the total number of 1212-digit numbers is 101210^{12}, we have:
A1012109<1011 |A| \leq \frac{10^{12}}{109} < 10^{11}

But the problem claims that 101110^{11} is possible.

Let us construct AA as follows:
Let AA be the set of all 1212-digit numbers where the sum of the digits is congruent to 00 modulo 1010.

For any two distinct elements x,yAx, y \in A, their digit sums are both 00 modulo 1010. If xx and yy differ in only one digit, say at position ii, then the sum of digits of xx and yy would differ by a nonzero amount, so their sums modulo 1010 would be different, which is a contradiction. Therefore, any two elements of AA differ in at least 22 digits.

How many such numbers are there? For any choice of the first 1111 digits, the last digit is determined modulo 1010 to make the sum 00 modulo 1010. So, 101110^{11} such numbers.

Therefore, the maximal possible number is 101110^{11}.

Thus, the answer is 101110^{11}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.