Maths Olympiad Prep

Library / /368 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

On planet Zork there are some cities. For every city there is a city at the diametrically opposite point. Certain roads join the cities on Zork. If there is a road between cities PP and QQ, then there is also a road between the cities PP' and QQ' diametrically opposite to PP and QQ. In plus, the roads do not cross each other and for any two cities PP and QQ it is possible to travel from PP to QQ.

The prices of Kriptonita in Urghs (the planetary currency) in two towns connected by a road differ by at most 100. Prove that there exist two diametrically opposite cities in which the prices of Kriptonita differ by at most 100 Urghs.

Solution

To solve this problem, we need to show that there exist two diametrically opposite cities on planet Zork where the prices of Kriptonita differ by at most 100 Urghs. We will use the properties of the roads and the cities given in the problem.

1. Graph Representation:
- Represent the cities on planet Zork as vertices of a graph G G .
- Represent the roads between the cities as edges of the graph G G .
- Since for every city P P there is a diametrically opposite city P P' , we can consider an automorphism ϕ \phi of order 2 on the graph G G such that ϕ(P)=P \phi(P) = P' .

2. Properties of the Graph:
- The graph G G is connected, meaning there is a path between any two cities P P and Q Q .
- If there is a road between cities P P and Q Q , then there is also a road between P P' and Q Q' .
- The roads do not cross each other.

3. Price Difference Constraint:
- The prices of Kriptonita in two towns connected by a road differ by at most 100 Urghs.

4. Constructing the Argument:
- Consider the function f:V(G)R f: V(G) \to \mathbb{R} where f(P) f(P) represents the price of Kriptonita in city P P .
- For any edge (P,Q)E(G) (P, Q) \in E(G) , we have f(P)f(Q)100 |f(P) - f(Q)| \leq 100 .

5. Using the Automorphism:
- Since ϕ \phi is an automorphism of order 2, it maps each city P P to its diametrically opposite city P P' .
- We need to show that there exist cities P P and P P' such that f(P)f(P)100 |f(P) - f(P')| \leq 100 .

6. Proof by Contradiction:
- Assume for contradiction that for all cities P P , f(P)f(P)>100 |f(P) - f(P')| > 100 .
- Consider a path P=P0,P1,P2,,Pn=P P = P_0, P_1, P_2, \ldots, P_n = P' from P P to P P' in the graph G G (such a path exists because G G is connected).
- By the price difference constraint, we have:
f(Pi)f(Pi+1)100for all i=0,1,2,,n1. |f(P_i) - f(P_{i+1})| \leq 100 \quad \text{for all } i = 0, 1, 2, \ldots, n-1.
- Summing these inequalities along the path, we get:
f(P)f(P)100×n. |f(P) - f(P')| \leq 100 \times n.
- Since f(P)f(P)>100 |f(P) - f(P')| > 100 by assumption, this leads to a contradiction if n=1 n = 1 (i.e., P P and P P' are directly connected by a road).

7. Conclusion:
- Therefore, our assumption must be false, and there must exist at least one pair of diametrically opposite cities P P and P P' such that f(P)f(P)100 |f(P) - f(P')| \leq 100 .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.