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 and , then there is also a road between the cities and diametrically opposite to and . In plus, the roads do not cross each other and for any two cities and it is possible to travel from to .
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 .
- Represent the roads between the cities as edges of the graph .
- Since for every city there is a diametrically opposite city , we can consider an automorphism of order 2 on the graph such that .
2. Properties of the Graph:
- The graph is connected, meaning there is a path between any two cities and .
- If there is a road between cities and , then there is also a road between and .
- 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 where represents the price of Kriptonita in city .
- For any edge , we have .
5. Using the Automorphism:
- Since is an automorphism of order 2, it maps each city to its diametrically opposite city .
- We need to show that there exist cities and such that .
6. Proof by Contradiction:
- Assume for contradiction that for all cities , .
- Consider a path from to in the graph (such a path exists because is connected).
- By the price difference constraint, we have:
- Summing these inequalities along the path, we get:
- Since by assumption, this leads to a contradiction if (i.e., and 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 and such that .