Problem #PRU-109574

Problems Methods Mathematical induction Mathematical induction (other) Pigeonhole principle Pigeonhole principle (other)

Problem

On a particular day it turned out that every person living in a particular city made no more than one phone call. Prove that it is possible to divide the population of this city into no more than three groups, so that within each group no person spoke to any other by telephone.