A group of 100 knights arrived at a tournament. Each knight knew at least 67 other knights. Show that there exists 4 knights that mutually know each other.
I know how to prove small amounts of people with a diagram by drawing lines to each other person and coloring them to represent do/don't know, but I obviously can't draw a diagram for this.
Take one knight, Sir Arthur. He has at least $67$ friends, so we can take one of them, who is called Sir Loin of Beef.
Of the remaining $98$, Sir Arthur known at least $66$, and so does Sir Beef. Therefore the overlap between their circles of aquaintances has to be at least $34$. From those $34$, pick one and call him Sir Cumference.
Of the remaining $97$ knights, at least $33$ are mutual aquaintances of Sir Arthur and Sir Beef, while at least $65$ are known to Sir Cumference. Those two groups must overlap by at least one knight, say Sir Duke.
The knights Sir Arthur, Sir Beef, Sir Cumference and Sir Duke all know each other.