Drawing Blanks

Premature Optimization is a Prerequisite for Success

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:

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.

Repeat.

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.

Advertisements

Written by bbzippo

01/27/2013 at 11:47 pm

Posted in fun, math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: