XXXV OM - III - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Miejscowości $P_1,\ldots, P_{1025}$ są obsługiwane przez linie lotnicze $A_1, \ldots, A_{10}$ , przy czym dla każdych miejscowości $P_k$ i $P_m$ ( $k \neq m$ ) istnieje taka linia, której samoloty latają bezpośrednio z $P_k$ do $P_m$ oraz bezpośrednio z $P_m$ do $P_k$ . Udowodnić, że któraś z tych linii może oferować podróż z nieparzystą liczbą lądowań rozpoczynającą i kończącą się w tej samej miejscowości.

Rozwiązanie

Przypuśćmy, że żadna z linii $A_1, \ldots, A_{10}$ nie może oferować podróży z nieparzystą liczbą lądowań, która zaczynałaby i kończyła się w tej samej miejscowości. Wynika stąd, że jeśli z miejscowości $P_k$ do miejscowości $P_m$ istnieje połączenie samolotami pewnej linii, przy którym jest parzysta liczba lądowań, to przy każdym innym połączeniu z $P_k$ do $P_m$ samolotami tej samej linii również jest parzysta liczba lądowań.

Dla każdej linii $A_j$ możemy zbiór miast podzielić w następujący sposób na dwa podzbiory $M_j$ i $N_j$ . Ustalamy dowolne miasto, np. $P_1$ i zaliczamy je do podzbioru $M_j$ . Następnie każde miasto, do którego można dolecieć z $P_1$ samolotami linii $A_j$ z parzystą liczbą lądowań zaliczamy do $M_j$ , natomiast każde miasto, do którego można dolecieć z $P_1$ samolotami linii $A_j$ z nieparzystą liczbą lądowań zaliczamy do $N_j$ . Jeśli po tym podziale pozostaną jeszcze pewne miasta, to dowolnie wybrane z nich, np. $P_k$ zaliczamy do $M_j$ wraz z tymi wszystkimi miastami, do których samoloty linii $A_j$ docierają z $P_k$ po parzystej liczbie lądowań. Te miasta, do których samoloty linii $A_j$ lecą z $P_k$ z nieparzystą liczbą lądowań zaliczamy do $N_j$ . Postępowanie to kontynuujemy, aż do wyczerpania wszystkich miast. Jeden ze zbiorów $M_1$ lub $N_1$ ma nie mniej niż $513$ elementów. Są to miasta nie mające między sobą bezpośrednich połączeń samolotami linii $A_1$ (dwa miasta, między którymi istnieje połączenie samolotami linii $A_1$ z nieparzystą liczbą lądowań, a więc w szczególności z jednym lądowaniem, należą do różnych zbiorów). Spośród tych $513$ miast nie mniej niż $257$ należy do jednego ze zbiorów $M_2$ albo $N_2$ . Żadne dwa spośród tych $257$ miast nie mają bezpośredniego połączenia samolotami linii $A_1$ oraz $A_2$ . Nie mniej niż połowa spośród nich,tj. $129$ miast należy do jednego ze zbiorów $M_3$ albo $N_3$ . Między żadnymi dwoma spośród tych $129$ miast nie ma bezpośredniego połączenia samolotami linii $A_1$ , $A_2$ , $A_3$ . Rozumując tak dalej stwierdzamy, że istnieje $65$ miast, między którymi nie ma żadnego bezpośredniego połączenia samolotami linii $A_1$ , $A_2$ , $A_3$ i $A_4$ , dalej - $33$ miasta bez bezpośredniego połączenia samolotami linii $A_1, \ldots, A_5$ , następnie $17$ miast nie mających bezpośredniego połączenia samolotami linii $A_1,\ldots, A_6$ . 9 spośród tych miast nie ma bezpośredniego połączenia samolotami linii $A_1, \ldots, A_7$ , $5$ z nich nie ma bezpośredniego połączenia samolotami $A_1, \ldots, A_8$ , $3$ miasta nie mają żadnego bezpośredniego rejsu żadnym samolotem linii $A_1, \ldots, A_9$ , wreszcie dwa miasta nie mają żadnego połączenia bezpośredniego samolotem żadnej z rozważanych dziesięciu linii. Ostatnie zdanie pozostaje jednak w sprzeczności z założeniem. Do sprzeczności tej doprowadziło przypuszczenie, że żadna linia nie może oferować podróży z nieparzystą liczbą lądowań zaczynającej i kończącej się w tej samej miejscowości. Zatem pewna linia może oferować taką podróż.