edited by
335 views
4 votes
4 votes

Let $\text{S} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}.$ What is the possible value of integer $\text{K}$ such that any subset of $\text{S}$ of size $\text{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?$

  1. $8$
  2. $6$
  3. $7$
  4. $5$
edited by

1 Answer

3 votes
3 votes
We must have two disjoint pairs of elements such that their sum is $9.$ Total such pairs possible is $5.\; \{0,9\}, \{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}$

So, we can apply pigeon hole principle, in worst case, select one element from each pair and then if we select $2$ more elements then we are guaranteed to have a set which 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.$
Answer:

Related questions

4 votes
4 votes
3 answers
3
5 votes
5 votes
3 answers
4