CombinatoricsDifficulty 7.7Prove itIMO Hk TST · Hong Kong
There is a set of n 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≥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.
No, it is not possible. Indeed, let ni be the number of 01-sequences in the set with 1 at the ith entry, where 1≤i≤200. We also let S 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(2n). On the other hand, there are ni(n−ni) pairs of different digits in the ith entry. Thus, by considering the ith positions of all pairs of 01-sequences, we have S=∑i=1200ni(n−ni). Using the AM-GM inequality, we have ni(n−ni)≤(2ni+(n−ni))2=4n2. Hence we have 50n2=i=1∑2004n2≥S≥101(2n). This implies n≤101. However, when n=101, the inequality 4n2≥ni(n−ni) is strict, as one side is an integer and the other side is not. Thus n<101, or n≤100.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.