NL-NWO 2016 Problem 1

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