Let $S_i$ be a subset of $S=\{1,2,\ldots,n\}$ for $i = 1,2,\ldots,n-1$. Prove that there exists a nonempty subset $R$ of $S$ such that $|S_i\cap R|\neq1$ for each $i=1,2,\ldots,n-1$.
about a existence of a combinatory subset problem
0
$\begingroup$
combinatorics
-
0sorry! I did not make this problem clear. First,$n-1$means there are n-1 subset $S_1,\cdots,S_{n-1}$, and it does not mean $S_i$ has n-1 elements. Second, we assume $R$ is not null set. I am sorry for that. – 2012-03-09
1 Answers
3
Presuming the proposition is:
If $S_1, S_2, \dots , S_{n-1}$ are $n-1$ distinct subsets of $S = \{1,2,\dots,n\}$, then there exists a non-empty subset $R$ of $S$ such that $|S_i \cap R| \neq 1$.
I believe induction works.
If each $|S_i| \neq 1$ for all $i$, then $S = R$ works.
Else, consider all $S_j$ such that $|S_j| = 1$ and delete those singleton elements from the other $S_i$ and from $S$, remove the $S_j$ and proceed inductively.
-
0@YILI: You are welcome. – 2012-03-09