## Archive for **January 2013**

## 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.

I’ve mentioned them a couple of times explicitly or implicitly: in Crocodile Dinner, in Important Theorems From Combinatorics, in the Crossing Lines problem and in its “anime variation”.

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: