IMO Shortlist 2004 problem C3
Kvaliteta:
Avg: 0,0Težina:
Avg: 7,0 In a country there are
cities. We can add a street between
cities
and
, iff there exist
cities
and
different from
and
such that there is no street between
and
,
and
, and
and
. 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
, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on
vertices (where each pair of vertices are joined by an edge).
![n>3](/media/m/c/b/e/cbef1f7ac5b499f3987506d46938e285.png)
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
![X](/media/m/9/2/8/92802f174fc4967315c2d8002c426164.png)
![Y](/media/m/3/b/c/3bc24c5af9ce86a9a691643555fc3fd6.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
![X](/media/m/9/2/8/92802f174fc4967315c2d8002c426164.png)
![X](/media/m/9/2/8/92802f174fc4967315c2d8002c426164.png)
![Y](/media/m/3/b/c/3bc24c5af9ce86a9a691643555fc3fd6.png)
![Y](/media/m/3/b/c/3bc24c5af9ce86a9a691643555fc3fd6.png)
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
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}](/media/m/5/2/d/52d043b0da37194c8c362dd541797acd.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Izvor: Međunarodna matematička olimpijada, shortlist 2004