Bakayev E.B.

In the country, there are 100 cities, and non-stop flights operate between any two cities. All flights are paid and cost a positive (possibly non-integer) number of tugriks. For any pair of cities A and B, the flight from A to B costs the same as the flight from B to A. The average cost of a flight is 1 tugrik. A traveler wants to fly around some $m$ different cities in $m$ flights, starting and ending in his hometown. Can he always manage to make such a trip, spending no more than $m$ tugriks on tickets, if

$$
\text { a) } m=99 \text {; }
$$

b) $m=100$ ?
a) Let all 99 flights from the home city cost 49.6 tugriks each. This is possible since the total cost of all flights (regardless of direction) is $99 \cdot 50$ tugriks. Then, to fly out of the home city and return to it, one would already need to spend more than 99 tugriks.
b) Consider all 99! possible circular routes. In total, each possible flight (considering direction) is used 98! times. Therefore, the total cost of all these routes is 98!$\cdot$99$\cdot$100 tugriks, and the average cost of a route is 100 tugriks. Thus, there will be a route that costs no more than 100 tugriks.

## Answer

a) Not always b) always.