IMO Shortlist 1986 problem 8


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 0,0
Dodao/la: arhiva
2. travnja 2012.
LaTeX PDF
From a collection of n persons q distinct two-member teams are selected and ranked 1, \cdots, q (no ties). Let m be the least integer larger than or equal to 2q/n. Show that there are m distinct teams that may be listed so that :
(i) each pair of consecutive teams on the list have one member in common and
(ii) the chain of teams on the list are in rank order.

Alternative formulation.
Given a graph with n vertices and q edges numbered 1, \cdots , q, show that there exists a chain of m edges, m \geq \frac{2q}{n} , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
Izvor: Međunarodna matematička olimpijada, shortlist 1986