Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.