Problem

Source: Dutch NMO 2016 p1

Tags: combinatorics, Coloring



(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.