The $25$ member states of the European Union set up a committee with the following rules: 1) the committee should meet daily; 2) at each meeting, at least one member should be represented; 3) at any two different meetings, a different set of member states should be represented; 4) at $n^{th}$ meeting, for every $k<n$, the set of states represented should include at least one state that was represented at the $k^{th}$ meeting. For how many days can the committee have its meetings?
Problem
Source: Baltic Way 2004, problem 13
Tags: combinatorics unsolved, combinatorics
grobber
20.11.2004 18:42
looks like we're interested in the maximal number of subsets of a set with $n$ elements (here $n=25$) s.t. each two have non-void intersection. I think this number is $2^{n-1}$. First of all, $2^{n-1}$ works, since we can take all the sets having containing a certain element. On the other hand, this number is maximal, because if we have a set, we exclude its complement, so the number of sets we don't have is at least as large as the number of sets we have, meaning that our family of chosen sets has at most $\frac{\mathcal P}2=2^{n-1}$ elements ($\mathcal P$ is the set of subsets of our set). Am I wrong?
Megus
20.11.2004 21:03
You're absolutely right The answer is $2^{24}$
yangzhe1990
24.03.2006 14:52
Yes, You Are Right. Could I Ask A Similar Problem? (Maybe obvious, but I can't prove it) Determine the max value of integer n such that There Exist n SubSet of Set S that none of them is subset of another.