Математикадан республикалық олимпиада, 2000-2001 оқу жылы, 9 сынып

Цорк деген сфералық планетасында бірнеше қала және осы қалаларды байланыстыратын әуежолдар бар. Кез келген қаланың достас қаласы бар (екі достас қалалар бір-біріне планетаның центріне қарағанда симметриялы орналасқан). Егер екі $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$-ая вершина соединены авиелинией. Доказано.