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.

by Top Rated User (1.2m points)

Related questions

1 answer
asked Apr 7, 2021 in Other Math Topics by Thatsd12 | 756 views
1 answer
asked Apr 5, 2021 in Other Math Topics by Thatsd12 | 642 views
1 answer
asked Mar 20, 2021 in Other Math Topics by algebrakid69 Level 1 User (120 points) | 486 views
1 answer
asked Nov 26, 2020 in Other Math Topics by anonymous | 579 views
1 answer
asked Jun 8, 2020 in Other Math Topics by ainm Level 1 User (220 points) | 558 views
1 answer
asked Jun 8, 2020 in Other Math Topics by ainm Level 1 User (220 points) | 552 views
1 answer
asked Dec 7, 2017 in Other Math Topics by Omar brown | 1.0k views
1 answer
1 answer
asked Sep 10, 2014 in Other Math Topics by anonymous | 880 views
Welcome to MathHomeworkAnswers.org, 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!
87,516 questions
100,297 answers
2,420 comments
744,996 users