Drawing Blanks

Premature Optimization is a Prerequisite for Success

Archive for January 2013

Antichains: Crocodiles and schoolgirls in parliament

leave a comment »

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:

Read the rest of this entry »


Written by bbzippo

01/27/2013 at 11:47 pm

Posted in fun, math