Problem

Source: 2017 FKMO Day 2 Problem 6

Tags: combinatorics



A room has $2017$ boxes in a circle. A set of boxes is friendly if there are at least two boxes in the set, and for each boxes in the set, if we go clockwise starting from the box, we would pass either $0$ or odd number of boxes before encountering a new box in the set. $30$ students enter the room and picks a set of boxes so that the set is friendly, and each students puts a letter inside all of the boxes that he/she chose. If the set of the boxes which have $30$ letters inside is not friendly, show that there exists two students $A, B$ and boxes $a, b$ satisfying the following condition. (i). $A$ chose $a$ but not $b$, and $B$ chose $b$ but not $a$. (ii). Starting from $a$ and going clockwise to $b$, the number of boxes that we pass through, not including $a$ and $b$, is not an odd number, and none of $A$ or $B$ chose such boxes that we passed.