XXXV OM - III - Zadanie 6

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óż.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź