# about a existence of a combinatory subset problem

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$.

-
Why does taking $R = S$ not work? (Perhaps I don't understand the meaning of $(n-1)$ subset, but I think it is just a subset with $n-1$ elements.) – arjafi Mar 9 '12 at 18:07
Also, regardless of what the $S_i$ have to satisfy, $R = \emptyset$ trivially works. – TMM Mar 9 '12 at 18:09
sorry! 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. – YI LI Mar 9 '12 at 18:54

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.

-
Thank you so much! That is what I want! Thank you! – YI LI Mar 9 '12 at 19:01
@YILI: You are welcome. – Aryabhata Mar 9 '12 at 21:46