There is a set of 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 ?
Solution
No, it is not possible. Indeed, let be the number of 01-sequences in the set with 1 at the th entry, where . We also let 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 . On the other hand, there are pairs of different digits in the th entry. Thus, by considering the th positions of all pairs of 01-sequences, we have . Using the AM-GM inequality, we have
Hence we have
This implies . However, when , the inequality is strict, as one side is an integer and the other side is not. Thus , or .
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.