Suppose X is a set of integers and |X| = 100. Prove there exists a subset Y ⊂ X such that |Y| = 34 and y ≡ y' (mod 3) for all y, y' ∈ Y.

In X we represent each element with its modulo 3 equivalent. There are only three possible values: 0, 1 and 2. Imagine each element of X to be a coloured ball where 0 is a red ball, 1 a white ball and 2 a blue ball. Each unique integer is imprinted on the appropriate coloured ball, depending on its modulo value. So we have a collection of balls instead of a set of integers. If all possible sets of 100 integers could be in X there would still only be red, white or blue balls. The subset Y has to be made up of balls of the same colour. We could by chance have 100 red balls, so any selection of red balls would make up subset Y just by selecting any 34 of these balls.

The worst case scenario would be an equal mixture of red, white and blue balls. So for 99 of the 100 integers we would have 33 balls of each colour. (Or in this selection of 99 balls, we could have 30 red balls, 33 white balls and 36 blue balls, etc.) In the worst case (33 balls of each colour) the 100th ball will give us 34 balls of one colour no matter what colour it is. Then we collect these 34 balls to create the subset Y such that all elements of Y have an equivalent modulo result. |y-y'|=3n (n is a positive integer, including zero) for all y,y'∈Y.

ago by Top Rated User (839k points)