MathDB

3

Part of 2002 Turkey MO (2nd round)

Problems(2)

Graph Airlines (GA)

Source: Turkey National Olympiad 2002 - D1 - P3

12/7/2009
Graph Airlines (GA) (GA) operates flights between some of the cities of the Republic of Graphia. There are at least three GA GA flights from each city, and it is possible to travel from any city in Graphia to any city in Graphia using GA GA flights. GA GA decides to discontinue some of its flights. Show that this can be done in such a way that it is still possible to travel between any two cities using GA GA flights, yet at least 2/9 2/9 of the cities have only one flight.
combinatorics unsolvedcombinatorics
Show that there exists real number d

Source: Turkey National Olympiad 2002 - D2 - P3

3/11/2011
Let nn be a positive integer and let TT denote the collection of points (x1,x2,…,xn)∈Rn(x_1, x_2, \ldots, x_n) \in \mathbb R^n for which there exists a permutation σ\sigma of 1,2,…,n1, 2, \ldots , n such that xσ(i)−xσ(i+1)≥1x_{\sigma(i)} - x_{\sigma(i+1) } \geq 1 for each i=1,2,…,n.i=1, 2, \ldots , n. Prove that there is a real number dd satisfying the following condition: For every (a1,a2,…,an)∈Rn(a_1, a_2, \ldots, a_n) \in \mathbb R^n there exist points (b1,…,bn)(b_1, \ldots, b_n) and (c1,…,cn)(c_1,\ldots, c_n) in TT such that, for each i=1,...,n,i = 1, . . . , n, a_i=\frac 12 (b_i+c_i) ,   |a_i - b_i|  \leq d,   \text{and}   |a_i - c_i| \leq d.
inductionalgebra unsolvedalgebra