The Problem Site : Problem Pages : High School Math


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?



Problem Moderated by: Graeme
Show Problem Solution

Options
Choose a Page
Login
Join The Site
High School Math
Current Problem
Previous Problem
Scores
About This Page

Subscribe
Archives
2008 Problems
2007 Problems
2006 Problems
2004 Problems
2003 Problems
2002 Problems
Problem Pages
Brainfood
High School Math
Calculus
The Maine Page
Games!
Math Games
Word Games
Strategy Games
All Games

The Problem Site : Problem Pages : High School Math