0
$\begingroup$

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

  • 0
    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.)2012-03-09
  • 1
    Also, regardless of what the $S_i$ have to satisfy, $R = \emptyset$ trivially works.2012-03-09
  • 0
    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.2012-03-09

1 Answers 1

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
    Thank you so much! That is what I want! Thank you!2012-03-09
  • 0
    @YILI: You are welcome.2012-03-09