Question

Let S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } . What is the smallest integer K such that any subset of S of size K contains two disjoint subsets of size two, { x 1 , x 2 } and { y 1 , y 2 } , such that x 1 + x 2 = y 1 + y 2 = 9?
(a) 8 (b) 9 (c) 7 (d) 6 (e) 5
answer of is cPLEASE explain how to solve it.?????

Answer 1

S = {0,1,2,3,4,5,6,7,8,9} with 10 members.

From S, we can choose two elements A={x1,x2} such that x1+x2=9, for example, 1 & 8.
We can also choose two elements B={y1,y2} such that y1+y2=9, for example, 2 & 7.
A and B are disjoint if there is no common elements between A and B.
We can find A and B readily from S, where K=10 (elements).

Suppose we take off ANY 1 element from S, so that we end up with a subset S(9) with 9 elements, we can still find A and B such that A and B are distinct, so S(9) works.

We continue to try K=8, or take off ANY two element from S, say 0 and 1. We can still find disjoint sets A and B (e.g. 3,6, 4,5) to satisfy the requirement. Try other combinations to convince yourself that K=8 works.

Similarly, convince yourself that K=7 works.

When we come to K=6, it will depend on which numbers we choose to take out from S.
If we take out (0,1,2,9), we still can find distinct sets A={3,6},B={4,5} to satisfy the requirement.
However, if we chose to take out {0,1,2,3} from S, leaving S(6)={4,5,6,7,8,9}, we can no longer find two disjoint sets A & B that satisfy x1+x2=9 AND y1+y2=9. Therefore we conclude that K=6 will not satisfy the requirement, and hence K=7 is the smallest number that satisfies the requirement.

Answer 2

Thanks a lot this solution is very helpful😀

Answer 3

You're welcome! :)