Six people: three friends or three strangers
Statement
- Prove that among any people, there are who are pairwise friends or who are pairwise strangers. (Friendship is mutual.)
- Show that cannot be replaced by .
Hint
Fix one person. Of the other five, how many are friends with them, or how many are strangers to them?
Show solutionHide solution
Solution
1. Colour each pair of the six people red (friends) or blue (strangers). Fix a person . Among the pairs containing , at least have the same colour; say red, towards .
- If one of the pairs , , is red, say , then are pairwise friends.
- Otherwise , , are all blue and are pairwise strangers.
The case of three blue pairs at is symmetric.
2. Put people on a regular pentagon: two people are friends if they are adjacent on the pentagon, strangers otherwise. Friends form the -cycle and strangers the "pentagram" cycle. Neither graph contains a triangle.
Lesson. A pigeonhole argument at one vertex, then a case analysis; extremal sharpness comes from a symmetric colouring.