Thread replies: 6
Thread images: 1
Thread images: 1
File: 1472002172784.jpg (600KB, 1065x1600px) Image search:
[Google]
600KB, 1065x1600px
Let [math]X[/math] be a set and let [math]A_1, ..., A_n \subset X[/math] be a collection of its subsets.
We want to find a collection [math]B_1, ..., B_m \subset X[/math] such that [math]\bigcup\limits_{i} B_i = X[/math] and [math]A_i \not\subseteq B_j[/math] for all [math]A_i, B_j[/math]. We also want to keep the number of [math]B[/math] sets as small as possible.
Now, in the worst case, how many [math]B[/math] sets do we need with respect to the number of [math]A[/math] sets? (Not homework, btw.)
>>
In the worst case, it's impossible. In the second worst case, [math]n[/math].
>>
>>9074241
If An is a singlet, you're fucked.
>>
>>9074241
Best case I can come up with is 2.
where all sets Ai are disconnected and are the union of partitions.
>>
>>9074241
Your problem is impossible. If [math] \ \forall i\in\overline{1,n}\ \forall j\in\overline{1,m}\ (A_i \not\subseteq B_j) [/math] then [math] \forall i\in\overline{1,n}\ \ A_i \not\subseteq \bigcup\limits_{j=1}^{m} B_j = X [/math] which is absurd. Maybe you meant something else?
>>
>>9075762
Disregard that, I suck cocks.
Thread posts: 6
Thread images: 1
Thread images: 1