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


Blogs on This Site
