Maths Olympiad Prep

Track / Stage 7 / 258 of 300 #2138 of 2444

Problem 2138

National Olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.7 Prove it IMO Hk TST · Hong Kong

There is a set of nn 01-sequences of length 200. Every pair of 01-sequences differ at least at 101 positions. (For example, the two 01-sequences of length 6, 111100 and 010001 differ at four positions, 1st, 3rd, 4th and 6th positions, counting from the left.) Is it possible that n101n \ge 101?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

No, it is not possible. Indeed, let nin_i be the number of 01-sequences in the set with 1 at the iith entry, where 1i2001 \le i \le 200. We also let SS be the total number of different positions between all pairs of 01-sequences in the set. Since every pair differs at least at 101 positions, we have S101(n2)S \ge 101 \binom{n}{2}. On the other hand, there are ni(nni)n_i(n - n_i) pairs of different digits in the iith entry. Thus, by considering the iith positions of all pairs of 01-sequences, we have S=i=1200ni(nni)S = \sum_{i=1}^{200} n_i(n - n_i). Using the AM-GM inequality, we have
ni(nni)(ni+(nni)2)2=n24. n_i(n - n_i) \le \left( \frac{n_i + (n - n_i)}{2} \right)^2 = \frac{n^2}{4}.
Hence we have
50n2=i=1200n24S101(n2). 50n^2 = \sum_{i=1}^{200} \frac{n^2}{4} \ge S \ge 101 \binom{n}{2}.
This implies n101n \le 101. However, when n=101n = 101, the inequality n24ni(nni)\frac{n^2}{4} \ge n_i(n - n_i) is strict, as one side is an integer and the other side is not. Thus n<101n < 101, or n100n \le 100.

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