« Vrati se
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.

Slični zadaci

#NaslovOznakeRj.KvalitetaTežina
1676IMO Shortlist 1986 problem 130
1674IMO Shortlist 1986 problem 110
1665IMO Shortlist 1986 problem 20
1259IMO Shortlist 1967 problem 31
1240IMO Shortlist 1966 problem 570
1237IMO Shortlist 1966 problem 540