Skip to main content
OlympiadHQ

Browse · MathNet

Print

XXI OBM

Brazil counting and probability

Problem

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 and then there is also a road connecting towns and , where is the antipode of and is the antipode of . Besides the roads do not cross each other and for any given two towns and it is possible to travel from to 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 be the prices of Kriptonita in the antipodal towns and respectively. Suppose that the prices differ by more than 100 Urghs at all antipodal towns. Thus for each . In a sequence of roads connecting to , we can find a road connecting and for some . Hence there exists a road connecting the antipodes and of and . If there exists a road connecting and , which implies , contradiction. If then On the other hand, we have which is a contradiction.

Techniques

Graph TheoryColoring schemes, extremal arguments