Archive for January 2013
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: