With $ |X| = 2n - 2$, by choose $ B_1 = \{1,2\}, B_2 = \{3,4\},..,B_{n - 1} = \{2n - 3,2n - 2\},B_n = \{1,3\}$ then not exist $ Y$ satisfy $ |Y| = n$ and $ |Y \cap B_i| \leq 1$ for all $ i = 1...n$ So $ |X| \geq 2n - 1$. We will prove that $ \min|X| = 2n - 1$ Indeed, choose subset $ Y$ such that $ |Y|$ max and $ |Y \cap B_i| \leq 1$ for all $ i = 1...n$ If $ |Y| \leq n - 1$ so $ |X - Y| \geq n$. Because with $ a \in (X - Y)$, exist $ 1 \leq t(a) \leq n$ and $ x_a \in Y$ satisfy $ (a,x_a) \in B_{t(a)}$ ( if not we can add $ a$ in $ Y$ and get $ |Y'| > |Y|$) Then if $ a \neq b$ so $ B_{t(a)} \neq B_{t(b)}$. Other hand $ |X - Y| \geq n$ so we have at least $ n$ subset $ B_{t(a)}$ different. So, $ |X - Y| = n$ And we can see subset $ X - Y$ satisfy $ |(X - Y) \cap B_i|=1$ for all $ i = 1..n$ and $ |X - Y| = n$ (absurd) So exist $ Y$ satisfy condition of problem

General, if $ |B_i|=m$ for all $ i=1..n$ ,we will get the result $ \min |X|=mn-1$. It's easy to prove

I think you mean $ \min \left|X\right| = m\left(n - 1\right) + 1$, right? And in your solution, I don't see why $ a\neq b$ should imply $ B_{t(a)}\neq B_{t(b)}$. We could have $ x_a=x_b$... darij

darij grinberg wrote: I think you mean $ \min \left|X\right| = m\left(n - 1\right) + 1$, right? And in your solution, I don't see why $ a\neq b$ should imply $ B_{t(a)}\neq B_{t(b)}$. We could have $ x_a = x_b$... darij Yes .$ \min |X|=(n-1)m+1$ If $ a\neq b$ so $ B_{t(a)} = \{a,x_a\},B_{t(b)} = \{b,x_b\}$. Because $ a,b \in X - Y, x_a,x_b \in Y$ so $ B_{t(a)} \neq B_{t(b)}$. What's rong??

tanlsth wrote: Because $ a,b \in X - Y, x_a,x_b \in Y$ so $ B_{t(a)} \neq B_{t(b)}$. How do you draw this conclusion? darij

1,2,3,........................

tanlsth, can you please try to fix your solution? Because mine is 3 pages long, after it has undergone a lot of error fixing (apparently it is very easy to make mistakes in this problem), and I still am not as sure of its validity as I usually am when I write down a detailed (unreadable) proof. You can find my proof at http://www.cip.ifi.lmu.de/~grinberg/subsetcond.pdf ; here are its cornerstones: Theorem 1. Let $ X$ be a set. Let $ n$ and $ m\geq1$ be two nonnegative integers such that $ \left\vert X\right\vert\geq m\left( n - 1\right) + 1$. Let $ B_{1}$, $ B_{2}$, ..., $ B_{n}$ be $ n$ subsets of $ X$ such that $ \left\vert B_{i}\right\vert \leq m$ for every $ i\in\left\{1,2,...,n\right\}$. Then, there exists a subset $ Y$ of $ X$ such that $ \left\vert Y\right\vert = n$ and $ \left\vert Y\cap B_{i}\right\vert \leq1$ for every $ i\in\left\{ 1,2,...,n\right\}$. Sketch of proof. Case 1 (when the union of the $ B_i$ covers all of $ X$) is very easy (by a counting argument, every set $ B_i$ contains an element which is not contained in any other $ B_j$, so you get your $ Y$), while Case 2 (when there is some $ x\in X$ which does not lie in any of the $ B_i$) is the actual argument, which mainly consists of replacing every $ B_i$ by $ B_i\setminus \left(B_{n + 1}\setminus\left\{\text{some fixed element of }B_{n + 1}\right\}\right)\setminus\left\{x\right\}$ and applying induction over $ n$ (noticing that $ B_{n + 1}$ itself collapses to a one-element set, and one-element sets can be ignored). Ah, and of course, it is obvious that $ m\left(n - 1\right) + 1$ is indeed the minimum (for $ m\left(n - 1\right)$, a counterexample can be easily found). PS. tanlsth, please tell me your real name in case you want it to be mentioned in the PDF. darij