Problem: In a room containing people, , at least one person has not shaken hands with everyone else in the room. What is the maximum number of people in the room that could have shaken hands with everyone else?
Answer Choices:
A.
B.
C.
D.
E. none of these
Solution:
Label the people as in such a way that and were a pair that did not shake hands with each other. Possibly every other pair of people shook hands, so that only and did not shake with everyone else. Therefore, at most people shook hands with everyone else.