IMO Shortlist 2004 problem C3


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 7,0
Dodao/la: arhiva
2. travnja 2012.
LaTeX PDF
In a country there are n>3 cities. We can add a street between 2 cities A and B, iff there exist 2 cities X and Y different from A and B such that there is no street between A and X, X and Y, and Y and B. Find the biggest number of streets one can construct!

Official Wording The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer {n\ge 4}, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on n vertices (where each pair of vertices are joined by an edge).
Izvor: Međunarodna matematička olimpijada, shortlist 2004