Maths Olympiad Prep

Track / Stage 7 / 258 of 300 #2298 of 2604

Problem 2298

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 n≥101n \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 1≤i≤2001 \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 S≥101(n2)S \ge 101 \binom{n}{2}. On the other hand, there are ni(n−ni)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(n−ni)S = \sum_{i=1}^{200} n_i(n - n_i). Using the AM-GM inequality, we have
ni(n−ni)≤(ni+(n−ni)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=1200n24≥S≥101(n2). 50n^2 = \sum_{i=1}^{200} \frac{n^2}{4} \ge S \ge 101 \binom{n}{2}.
This implies n≤101n \le 101. However, when n=101n = 101, the inequality n24≥ni(n−ni)\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 n≤100n \le 100.

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