Maths Olympiad Prep

Library / /5 of 6

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 PP' and QQ', where PP' is the antipode of PP and QQ' 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 aibia_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 aibi>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 ajbj100a_j - b_j \le 100, contradiction.
If jkj \ne k then
ajbk100akbj100    aj+akbjbk200 \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
ajbj>100akbk>100    aj+akbjbk>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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.