Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /102 of 120

Brazilian Mathematical Olympiad

Combinatorics Difficulty 6.3 National Olympiad Prove it Brazil

Planet Zork is spherical and has many towns. For each town there is a corresponding antipodal town (i.e. symmetric in relation to the centre of the planet).
There are roads connecting pairs of towns in Zork. If there is a road connecting towns PP and QQ then there is also a road connecting towns P′P' and Q′Q', where P′P' is the antipode of PP and Q′Q' is the antipode of QQ. Besides the roads do not cross each other and for any given two towns PP and QQ it is possible to travel from PP to QQ through some sequence of roads.
The prices of Kriptonita in Urghs (the planetary currency) in two towns connected by a road differ by no more than 100 Urghs. Prove that there exist two antipodal towns such that the prices of Kriptonita in these towns differ by no more than 100 Urghs.

Solution

Let ai≥bia_i \ge b_i be the prices of Kriptonita in the antipodal towns AiA_i and BiB_i respectively. Suppose that the prices differ by more than 100 Urghs at all antipodal towns. Thus ai−bi>100a_i - b_i > 100 for each ii.
In a sequence of roads connecting A0A_0 to B0B_0, we can find a road connecting AjA_j and BkB_k for some j,kj, k. Hence there exists a road connecting the antipodes BjB_j and AkA_k of AjA_j and BkB_k.
If j=kj = k there exists a road connecting AjA_j and BjB_j, which implies aj−bj≤100a_j - b_j \le 100, contradiction.
If j≠kj \ne k then
∣aj−bk≤100ak−bj≤100  ⟹  aj+ak−bj−bk≤200 \left| \begin{array}{l} a_j - b_k \le 100 \\ a_k - b_j \le 100 \end{array} \right. \implies a_j + a_k - b_j - b_k \le 200
On the other hand, we have
∣aj−bj>100ak−bk>100  ⟹  aj+ak−bj−bk>200, \left| \begin{array}{l} a_j - b_j > 100 \\ a_k - b_k > 100 \end{array} \right. \implies a_j + a_k - b_j - b_k > 200,
which is a contradiction.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.