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 Other Math Topics by

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.

1 Answer

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)

Related questions

0 answers
asked 5 days ago in Other Math Topics by Thatsd12 | 29 views
1 answer
asked Apr 5 in Other Math Topics by Thatsd12 | 58 views
1 answer
asked Mar 20 in Other Math Topics by algebrakid69 Level 1 User (120 points) | 75 views
1 answer
1 answer
asked Jun 8, 2020 in Other Math Topics by ainm Level 1 User (220 points) | 50 views
1 answer
asked Jun 8, 2020 in Other Math Topics by ainm Level 1 User (220 points) | 95 views
Welcome to, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!
86,303 questions
92,362 answers
23,927 users