Maths Olympiad Prep

Library / /53 of 136

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it 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?

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.

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.