Drawing Blanks

Premature Optimization is a Prerequisite for Success

Applied Type Theory

with one comment

Here is a fun little problem that is kind of related to Russell’s type theory.

100 crocodiles got together for a dinner. And they started to swallow one another. When the feast was over, one could observe that among any 10 of the crocodiles there had been an act of cannibalism. Prove that there exists a chain of 12 nested crocodiles.

Solution.

Some of the crocodiles were either vegetarian or too slow, so they didn’t eat anyone. Let’s call them Type0 crocodiles. Those who ate only Type0 guys are called Type1. Those who ate only Type0 and Type1 belong to  Type2, and so on.

Obviously, if one crocodile swallowed another then the type of the swallower is greater than the type of the swalowee. Therefore, it’s impossible to find 10 crocodiles that belong to the same type. And with the maximum of 9 members per type, and the total number of crocodiles being 100, we need at least 12 different types. (11 is not enough: 11*9=99). So there is at least one Type11 crocodile who earned his title by eating at least one Type10 crocodile, etc. QED.

croctypes

The animal-friendly formulation is: In a partially ordered set of m*n+1 elements, there either exists a chain of m+1 elements or an anti-chain of n+1 elements. A chain is a subset where any two elements are comparable, and an anti-chain is a subset where no elements are comparable.

Advertisements

Written by bbzippo

01/08/2010 at 6:56 am

Posted in math

One Response

Subscribe to comments with RSS.

  1. […] leave a comment » Here is a simple problem that requires an approach somewhat similar to what we used to solve the crocodile problem here https://bbzippo.wordpress.com/2010/01/08/applied-type-theory/ […]


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: