View topic - subset conditions • Art of Problem Solving

Page 1 of 1

[ 8 posts ]

Author

Message

Jumbler

Posts: 348

Posted: Nov 07, 2006, 8:27 am • # 1

Given a positive integer $n\geq 2$ , let $B_{1}$ , $B_{2}$ , ..., $B_{n}$ denote $n$ subsets of a set $X$ such that each $B_{i}$ contains exactly two elements. Find the minimum value of $\left|X\right|$ such that for any such choice of subsets $B_{1}$ , $B_{2}$ , ..., $B_{n}$ , there exists a subset $Y$ of $X$ such that:
(1) $\left|Y\right| = n$ ;
(2) $\left|Y \cap B_{i}\right|\leq 1$ for every $i\in\left\{1,2,...,n\right\}$ .

tanlsth

Posts: 46
Location: Viet Nam

Posted: Mar 19, 2009, 12:38 am • # 2

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

tanlsth Posts: 46 Location: Viet Nam	Posted: Mar 19, 2009, 12:48 am • # 3 General, if $\|B_i\|=m$ for all $i=1..n$ ,we will get the result $\min \|X\|=mn-1$ . It's easy to prove

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 19, 2009, 7:58 am • # 4

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

tanlsth

Posts: 46
Location: Viet Nam

Posted: Mar 22, 2009, 12:49 pm • # 5

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?? :lol:

darij grinberg Posts: 5937 Location: Karlsruhe / Munich	Posted: Mar 23, 2009, 4:49 pm • # 6 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 _________________ Now the die is cast, the first step taken, a glimmer of hope lights up our lives Visions of the past, dreams forsaken forming right under our eyes We are alive...

Tanequil Posts: 24	Posted: Mar 24, 2009, 10:21 am • # 7 1,2,3,........................

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Apr 06, 2009, 10:26 am • # 8

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

Display posts from previous: Sort by

Share on Facebook

Previous topic | Next topic

Community » Olympiad Section » Combinatorics » Combinatorics Unsolved Problems

All times are UTC - 8 hours [ DST ]

Moderators: MithsApprentice, N.T.TUAN, Peter, darij grinberg, orl, pbornsztein, freemind, Megus, High School Olympiad Moderators

Page 1 of 1

[ 8 posts ]

subset conditions

Login