Maths WorkshopMaths problems with full solutions
Exercise 637Combinatorics › Pigeonhole principleM1Added 5 Nov 2026

Six people: three friends or three strangers

#Ramsey theory#pigeonhole#colouring

Statement

  1. Prove that among any 66 people, there are 33 who are pairwise friends or 33 who are pairwise strangers. (Friendship is mutual.)
  2. Show that 66 cannot be replaced by 55.
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 vv. Among the 55 pairs containing vv, at least 33 have the same colour; say red, towards a,b,ca,b,c.
- If one of the pairs abab, bcbc, caca is red, say abab, then v,a,bv,a,b are pairwise friends.
- Otherwise abab, bcbc, caca are all blue and a,b,ca,b,c are pairwise strangers.

The case of three blue pairs at vv is symmetric.

2. Put 55 people on a regular pentagon: two people are friends if they are adjacent on the pentagon, strangers otherwise. Friends form the 55-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.