1
$\begingroup$

(Adapted) (Mathematical Circles) Eleven students formed five study groups. Prove that we can find two students, say A and B, that every study group that includes student A also includes student B

One solution is to name every group as $1,\dots ,5$ and then say that every student must be in a subset of $\{1,\dots, 5\}$. Then rearrange these subsets in other sets. Say that set $A$ is one of those other sets. $A$ is such that if two students are in the same set, they must be in the same groups (every set element is a subset of a element of $A$). Example: $A = \{ \{1\}, \{1,2\}, \{1,2,3\}, \dots\}$. This way, we can apply the pidgeonhole principle and show that at least two students are in the same $A$.

However, this solution is not very intuitive. Is there any other solution?

$\endgroup$
  • $\begingroup$ To be clear, a group that includes student $B$ but not student $A$ would not disqualify the pairing? $\endgroup$ – Joffan Jan 19 '17 at 19:08
  • $\begingroup$ @Joffan iff all groups for all students A and B $\endgroup$ – Lucas Henrique Jan 20 '17 at 18:50
  • $\begingroup$ Let me ask again a different way. If we have such a pairing $A$ and $B$ as per the question, is it possible that there is a group that contains student $B$ but does not contain student $A$? $\endgroup$ – Joffan Jan 20 '17 at 18:56
  • $\begingroup$ There is. But only if we're talking about students A, ..., (student 11). There might be students with the property you said, but there are at least two that are in the same group $\endgroup$ – Lucas Henrique Jan 21 '17 at 2:36
  • 1
    $\begingroup$ My motivation is that it is relatively easy to make sure that no two students are always together - that is, they are always both in a group or both out of it. You can do that with only four groups. So I was trying to find out how the one-way relation works, exactly. $\endgroup$ – Joffan Jan 21 '17 at 3:11
1
$\begingroup$

So we have $11$ sets $A_1,...,A_{11}$ which are subsets of the set $S= \{1,2,3,4,5\}$. ($A_i$ represents i-th student and $j\in A_i$ iff the student $i$ is in the $j$-th group). We have to prove that there exist $A_m=:A$ and $A_n=:B$ such that if $k\in A$ then $k\in B$ i.e. $A\subset B$.

Say there is no such pair. But then we have an antichain $A_1,...,A_{11}$ which wide is $11$. But this is impossible by Sperner theorem which tell's us that in $S$ we have an antichain which is wide at most ${5\choose 2} = 10$. A contradiction.

$\endgroup$
0
$\begingroup$

I would look at it as a function $f$ from $[[11]]$ to $P([[5]])$ such that for all $a,b \in [[11]]$ $f(a) \not \subset f(b)$. Then with Dilworth's theorem you can see that there are at most $\binom{5}{3}=10$ anti-chains.

$\endgroup$
  • $\begingroup$ I never saw anything about antichains, just read about it today. However, this is basically the same solution for the problem but using set and equivalence abstraction $\endgroup$ – Lucas Henrique Jan 21 '17 at 2:18
  • $\begingroup$ I think the idea is basically the same, yes, but imo it makes for a way more intuitive proof if you write it out. $\endgroup$ – Micky Messer Jan 22 '17 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.