Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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.) –  Arthur Fischer Mar 9 '12 at 18:07
1  
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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.