2003 авиалинии




Скачать 39.87 Kb.
Дата25.07.2016
Размер39.87 Kb.

графы

В стране 1001 город. Некоторые пары городов соединены беспосадочными авиалиниями двух авиакомпаний. Известно, что пользуясь авиалиниями одной авиакомпании можно из любого города долететь до любого другого двумя различными способами (возможно, с пересадками), а пользуясь авиалиниями другой авиакомпании – тремя различными способами. Найдите наименьшее возможное количество авиалиний.

Ответ. 2003 авиалинии.

Решение.

Рассмотрим авиалинии той авиакомпании, пользуясь услугами которой из любого города в любой другой можно добраться ровно двумя способами. Если какой-то город соединен с другими городами менее чем двумя такими авиалиниями, то либо город изолирован от других городов (число авиалиний равно нулю), либо город соединен авиалинией только с каким-то городом (одна авиалиния). Но тогда не существует двух способов перелета из города в город , что противоречит условию. Следовательно, каждый город соединен с другими городами по меньшей мере двумя авиалиниями. Т.е. число авиалиний этой авиакомпании не меньше 1001.

Рассмотрим теперь авиалинии другой авиакомпании. Как уже было доказано, менее, чем 1001 авиалинии быть не может. Пусть число авиалиний равно 1001. Тогда каждый город соединен с двумя другими городами ровно двумя авиалиниями. Но это значит, что все города соединены авиалиниями последовательно (т.е.: первый город – со вторым, второй – с третьим, и. т.д., 1001-й город – с первым), иначе образуются изолированные группы городов и нельзя будет из города одной группы перелететь в какой-либо город другой группы. Однако, при последовательном соединении городов существует ровно два способа перелета из одного города в другой, что противоречит условии. Следовательно, авиалиний, с помощью которых из любого города в любой можно добраться ровно тремя способами, не менее 1002. Остается показать, что 1001 авиалиния в первом случае и 1002 авиалинии во втором случае удовлетворяют условию. Авиалинии первой компании соединяют последовательно се города: первый со вторым, второй – с третьим и т.д., 1001-й – с первым. Авиалинии второй компании также последовательно соединяют все города и добавляется еще одна авиалиния, повторно соединяющая какую-нибудь пару соседних городов (например, первый со вторым)

Следовательно, наименьшее число авиалиний равно 2003.

--------------------------------------------------------------------------------------------------------------------

На I Магнитогорском турнире юных математиков каждый из принимавших в нем участие школьников познакомился с 17 другими. Во втором турнире принимает участие на 25 школьников больше. Может ли случиться так, что за время проведения второго турнира каждый из участников познакомится с 23 другими? (?)



Ответ. Нет.

Решение.

Пусть на первом турнире было участников. Предположим, что при знакомстве школьники пожимали друг другу руки. Количество рукопожатий на первом турнире равно , а значит - четно, а - нечетно. Количество рукопожатий на втором турнире равно . Это число нецелое. Противоречие.

--------------------------------------------------------------------------------------------------------------------

Друзья при прощании обменялись фотографиями. Фотографий понадобилось 20. Сколько было друзей?



Ответ. 5.

Решение.

Каждый должен подарить на одну фотографию меньше, чем всего имеется друзей. Произведение двух последовательных числе равно 20, если большее из чисел равно 5.

--------------------------------------------------------------------------------------------------------------------

В стране 15 республик и в каждой республике 15 городов, не считая столицы. Внутри каждой республики некоторые пары городов соединены республиканскими авиалиниями, а некоторые столицы республик соединены между собой межреспубликанскими авиалиниями (два города различных республик, не являющиеся столицами, не соединены между собой). Известно, что из любого города страны в любой другой можно добраться, сделав не более двух пересадок. Найдите наименьшее возможное число авиалиний в стране.(Устинов А.В.)



Ответ. 330.

Решение. Каждый город некоторой республики должен быть напрямую соединен со столицей этой республики, иначе, чтобы добраться из этого города до какого-либо города (не столицы) другой республики, потребуется сделать не менее трех пересадок. По этой же причине любые две столицы должны быть соединены между собой. Таким образом, наименьшее число авиалиний в стране равно:

15 × 15 + (15 × 14) : 2 = 330.


--------------------------------------------------------------------------------------------------------------------
В стране несколько городов. Некоторые пары городов соединены дорогами, причем два города могут быть соединены не более чем одной дорогой. Известно, что из любого города страны можно проехать до любого другого (возможно, через другие города). Найдите наименьшее возможное число городов, если число дорог равно 2005.

Ответ. 64.

Решение. Если городов меньше 64, то их соединяет не больше (63 × 62) : 2 = 1903 дороги, значит городов не меньше 64.

--------------------------------------------------------------------------------------------------------------------

На некотором острове расположено 15 государств. Для каждого из них хотя бы одно соседнее государство – дружественное. Докажите, что найдется государство, у которого четное количество дружественных соседей. (Два государства называются соседними, если у них имеется целый кусок общей границы).( «Математика: Интеллектуальные марафоны, турниры, бои 5-11 классы: Книга для учителя. Авторский коллектив: Блинков А.Д., Семенов А.В. и др.»

Доказательство.

*********Предположим, что у каждого государства нечетное количество дружественных соседей, тогда, сложив 15 нечетных чисел, получим нечетное число. С другой стороны, государство А дружественно государству В, то и В дружественно А. Следовательно, найденная нами сумма должна быть четной. Из полученного противоречия следует, что наше предположение неверно и хотя бы у одного государства четное количество дружественных соседей, что и требовалось доказать.**********на графы

--------------------------------------------------------------------------------------------------------------------

В городе отличников от каждой площади отходит ровно пять улиц, причем каждая улица соединяет ровно две площади. Докажите, что количество площадей в этом городе четно, а количество улиц кратно пяти.



(Математика: Интеллектуальные марафоны, турниры, бои 5-11 классы: Книга для учителя. Авторский коллектив: Блинков А.Д., Семенов А.В. и др.)

Доказательство.

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


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница