(a) On a long pavement, a sequence of $999$ integers is written in chalk. The numbers need not be in increasing order and need not be distinct. Merlijn encircles $500$ of the numbers with red chalk. From left to right, the numbers circled in red are precisely the numbers $1, 2, 3, ...,499, 500$. Next, Jeroen encircles $500$ of the numbers with blue chalk. From left to right, the numbers circled in blue are precisely the numbers $500, 499, 498, ...,2,1$. Prove that the middle number in the sequence of $999$ numbers is circled both in red and in blue. (b) Merlijn and Jeroen cross the street and find another sequence of $999$ integers on the pavement. Again Merlijn circles $500$ of the numbers with red chalk. Again the numbers circled in red are precisely the numbers $1, 2, 3, ...,499, 500$ from left to right. Now Jeroen circles $500$ of the numbers, not necessarily the same as Merlijn, with green chalk. The numbers circled in green are also precisely the numbers $1, 2, 3, ...,499, 500$ from left to right. Prove: there is a number that is circled both in red and in green that is not the middle number of the sequence of $999$ numbers.
Problem
Source: Dutch NMO 2016 p1
Tags: combinatorics, Coloring
07.09.2019 12:36
(a)For brevity, we will say that a number encircled in red is a red number, and similarly for blue. So some numbers could be both red and blue. Since there are 999 numbers written on the pavement, of which 500 are red and 500 are blue, we have at least one bicoloured number by the pigeonhole principle. Consider such a bicoloured number and suppose it is the number k. From left to right, the red numbers form the sequence 1, 2, . . . , 500. Hence, to the left of the bicoloured number we have the red numbers 1 to k−1, and to the right we have the red numbers k + 1 to 500. The blue numbers are written in the opposite order: from left to right they form the sequence 500, 499, . . . , 1. To the left of the bicoloured number we therefore have the blue numbers k+1 to 500, and to the right we have the blue numbers 1 to k−1. We count how many numbers there are on each side of the bicoloured number. On the left we have the red numbers 1 to k − 1 and the blue numbers k + 1 to 500. Hence, there are at least 499 distinct numbers on the left. On the right we have the red numbers k + 1 to 500 and the blue numbers 1 to k − 1. Again at least 499 distinct numbers. Since there are only 999 = 499 + 1 + 499 numbers on the pavement, we have already considered all numbers on the pavement. We conclude that there are precisely 499 numbers on each side of the bicoloured number. The bicoloured number is therefore precisely in the middle of the sequence. (b) Just as in part (a), the pigeonhole principle yields that at least one number is bicoloured, i.e. both red and green. If more than one number is bicoloured, one of them is not exactly in the middle of the sequence and we are done. Therefore, it suffices to examine the case where there is exactly one bicoloured number. Let this number be k. Again, we count how many numbers there are on each side of the bicoloured number. On the left we have the red numbers 1 to k − 1 and the green numbers 1 to k − 1. Since none of these numbers is bicoloured, there are at least 2 · (k − 1) distinct numbers on the left. On the right we have the red numbers k + 1 to 500 and the green numbers k + 1 to 500. Since none of these numbers is bicoloured, we have at least 2 · (500 − k) distinct numbers on the right. Since 2·(k−1)+1+2·(500−k) = 999, we have already counted all numbers. On the left of the bicoloured number we therefore have exactly 2·(k−1) numbers, and on the right we have exactly 2 · (500 − k) numbers. Since 2 · (k − 1) is an even number, it is unequal to 499. We conclude that the bicoloured number is not exactly in the middle of the sequence.