Party Hardy
(Part A): There are 100 people in a ballroom. Every person knows at least 67 other people (and if I know you, then you know me). Prove that there is a set of four people in the room such that every two from the four know each other. (We will call such a set a "clique.")
(Part B): Two people in the room are Joe and Grace, who know each other. Is there a clique of four people which includes Joe and Grace?
(Part C): Oops, I miscounted. There are actually 101 people in the room, But it's still true that each knows at least 67 others. That can't make a difference, can it?
(Part A): There are 100 people in a ballroom. Every person knows at least 67 other people (and if I know you, then you know me). Prove that there is a set of four people in the room such that every two from the four know each other. (We will call such a set a "clique.")
(Part B): Two people in the room are Joe and Grace, who know each other. Is there a clique of four people which includes Joe and Grace?
(Part C): Oops, I miscounted. There are actually 101 people in the room, But it's still true that each knows at least 67 others. That can't make a difference, can it?
View the solution
It's Cotton Candy for the Mind
A Strong Will
Blogs on This Site
Reviews and book lists - books we love!
The site administrator fields questions from visitors.
Like us on Facebook to get updates about new resources