IMO Shortlist 2013 problem C6

  Avg: 3,0
  Avg: 8,0
Dodao/la: arhiva
21. rujna 2014.
In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible number of flights required to go from one of them to the other. It is known that for any city there are at most 100 cities at distance exactly three from it. Prove that there is no city such that more than 2550 other cities have distance exactly four from it.
Izvor: Russia