Antichains: Crocodiles and schoolgirls in parliament
Antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable.
Here is another elementary problem that is kind of in between “schoolgirl rivalry” and “crocodiles that swallow each other”.
Consider 435 persons. Assume that every one of them has lied to exactly one other person from this set. (assume they don’t lie to themselves).
Prove that it’s possible to find a subset of at least 145 people so that nobody in that subset has lied to nobody in that subset.
Solution follows after a short break:
Let P (parliament) be the set of 435 and C (committee) be the subset we want to select.
Consider a member m of P who is “least lied to”. This member has been lied to no more than once [proof: exercise for the reader].
Let us select m into C. Then, remove from P everybody who lied to m and everybody whom m lied to.
With each repetition, the size of C grows by 1, and the size of P is reduced by at most 3:
- one m “the least lied to” who goes into C
- at most one who lied to m
- exactly one whom m lied to.
So we can form C that contains at least 1/3 of P.