сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

В не­ко­то­рой стра­не 100 го­ро­дов и 146 авиа­ком­па­ний. Любые два го­ро­да со­еди­не­ны дву­сто­рон­ни­ми рей­са­ми одной или не­сколь­ких авиа­ком­па­ний. Сто­и­мость пе­ре­ле­та между го­ро­да­ми, со­еди­нен­ны­ми рей­са­ми k авиа­ком­па­ний, оди­на­ко­ва и со­став­ля­ет  дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби . Ока­за­лось, что не су­ще­ству­ет го­ро­дов, между ко­то­ры­ми с пе­ре­сад­кой можно до­брать­ся де­шев­ле, чем пря­мым рей­сом. До­ка­жи­те, что можно найти марш­рут с одной пе­ре­сад­кой, обе части ко­то­ро­го стоят оди­на­ко­во.

Спрятать решение

Ре­ше­ние.

На самом деле нам надо до­ка­зать, что су­ще­ству­ет два рейса оди­на­ко­вой цены из од­но­го го­ро­да. Пред­по­ло­жим про­тив­ное. Тогда все перелёты из лю­бо­го го­ро­да имеют раз­ную цену.

Рас­смот­рим самый до­ро­гой рейс. Он самый до­ро­гой в каж­дом из своих го­ро­дов, а зна­чит су­ще­ству­ет хотя бы 98 более дешёвых перелётов. Тогда этот самый до­ро­гой рейс имеет цену  дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби боль­ше или равно дробь: чис­ли­тель: 1, зна­ме­на­тель: 48 конец дроби , т. е. k мень­ше или равно 48 .

Воз­мож­ных сто­и­мо­стей, мень­ших  дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби , но не мень­ших  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 k конец дроби всего k. Зна­чит, в каж­дом из го­ро­дов, ко­то­рые со­еди­ня­ет самый до­ро­гой рейс, есть ещё не более k рей­сов не де­шев­ле  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 k конец дроби , то есть в сего их в этих двух го­ро­дах не более 2 k мень­ше или равно 96 (не счи­тая са­мо­го до­ро­го­го). Но это зна­чит, что в какой-то из остав­ших­ся 98 го­ро­дов из обоих кон­цов са­мо­го до­ро­го­го рейса ведут рейсы ценой ниже  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 k конец дроби . Сле­до­ва­тель­но, если мы вос­поль­зу­ем­ся этими двумя рей­са­ми, мы смо­жем про­ле­теть между кон­ца­ми са­мо­го до­ро­го­го рейса де­шев­ле, чем этим рей­сом, что про­ти­во­ре­чит усло­вию. По­лу­чен­ное про­ти­во­ре­чие до­ка­зы­ва­ет утвер­жде­ние за­да­чи.


Аналоги к заданию № 894: 902 Все