Республиканская олимпиада по математике, 2001 год, 9 класс

На сферической планете Цорк имеется несколько городов и авиалиний, соединяющих эти города. У каждого города имеется город-побратим (это город, который симметричен данному относительно центра планеты). Известно, что если существует авиалиния, соединяющая города $P$ и $Q$, тогда существует авиалиния, соединяющая города $P'$ и $Q'$, которые являются городами-побратимами для $P$ и $Q$ соответственно. Также известно, что из любого города можно попасть в любой другой, пользуясь авиалиниями. Стоимость тонны топлива в двух городах, соединяемых авиалинией, отличается не более чем на 50 золотых монет. Докажите, что найдутся два города-побратима, в которых стоимость тонны топлива отличается не более чем на 50 золотых монет.

Комментарий/решение

Докажем от противного. Предположим не найдутся 2 города-побратима, разница между которыми не более 50 монет. То есть любые 2 города-побратима отличаются более чем на 50 монет.

$\textbf{ТЕПЕРЬ ЗАМЕТИМ СВОЙСТВО}$: Рассмотрим 2 города которые соединены авиалинией. Тогда их соответсвующие-города побратимы тоже соединены авиалинией. Пусть в $P$ городе - $X$ монет, в $Q$ городе $X+K$ монет ($50\geq K>0$). Докажем что их города- побратимы оба больше либо оба меньше соответствующих им городов. То есть, либо монет в $P'>P, Q'>Q$ либо $P'<P,Q'<Q$. Докажем это тоже от противного.

$$1)P'<P;Q'>Q \rightarrow X-50> P'; Q'>X+K+50 \rightarrow Q'-P'>100+K>100$$ Противоречие,так как $Q'$ и $P'$ соединены авиалинией.

$$2)P'>P;Q'<Q \rightarrow P'>X+50;Q'<X+K-50 \rightarrow P'-Q'>100-K\geq 100-50 \geq 50$$ Тоже противоречие.

По условию задачи, можно добраться из любой планеты в любую другую планету. Посмотрим путь из планеты $Z$ в его планету-побратим - $Z'$. Очевидно что нету авиалинии $ZZ'$ так как мы поставили условие ,что они различаются более чем на 50 монет. Значит есть граф-дерево из $m+2$ вершин концами которого являются Z и Z'. Пусть $Z=a$ монет, тогда $m+1$- ая вершина графа =$a+k_1+...+k_m$ монет, где $|k_1|,...,|k_m|\leq50$. Так как $Z'$ соединена с $m+1$-ой вершиной графа, то город-побратим $m+1$-ой вершины графа соединена с $Z$. Заметим, что если $Z’>Z$, то город-побратим второй вершины графа тоже>соответствующей ей вершины (доказанное ранее свойство). Отсюда следует, что город-побратим $m+1$ вершины тоже > соответствующей ему города. Пусть,БОО $Z’>Z$.Тогда, город побратим $m+1$-ой вершины $>a+k_1+…+k_m+50\rightarrow 50 \geq$город $m+1$-ой вершины $-Z>50+a+k_1+…+k_m-a=50+k_1+…+k_m\rightarrow0>k_1+…+k_m$.

Теперь посмотрим разницу между $m+1$-ой вершиной графа и $Z’$. $Z’>50+a\rightarrow Z’-{m+1 вершина}>50-(k_1+…+k_m)>50$. Противоречие, так как $Z’$ и $m+1$-ая вершина соединены авиелинией. Доказано.