МАЛЫЙ МЕХМАТ МГУ

Кружок для старшеклассников, не участвовавших ранее в математических кружках

Занятие 7 (31 октября 2015 года). Пути-дороги

1.

a)

В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

б)

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

2.

В городе Маленьком 75 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с 35 другими?

3.

Максим поспорил с Петей на щелбан: он утверждал, что может построить систему из восьми городов и дорог между ними так, чтобы из этих городов выходило бы соответственно 7, 7, 7, 5, 3, 3, 2, 2 дороги (два города могут быть связаны не более чем одной дорогой). Объясните, почему так ехидно ухмыляется Петя.

4.

Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.

5.

Компания из нескольких друзей вела переписку так, что каждое письмо получали все, кроме отправителя. Каждый написал одно и то же количество писем, в результате чего всеми вместе было получено 440 писем. Сколько человек могло быть в этой компании?

6.

В некоторой стране 1225 городов, из каждого выходит не менее 612 дорог в другие города (по одной дороге в каждый город). Верно ли, что из каждого города можно добраться до каждого?

7.

В некотором государстве система авиалиний устроена так, что любой город соединён авиалиниями не более чем с тремя другими, и из любого города в любой другой можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?

8.

В городе есть дороги трёх типов: однополосные, двухполосные и трехполосные. На каждом перекрёстке в городе сходятся три дороги, причём разных типов. Иными словами, каждый перекрёсток есть разделение трёхполосной дороги на двухполосную и однополосную. Тупиков в городе нет. Три городских дороги выходят за пределы города и превращаются в шоссе. Докажите, что из города выходит ровно по одному шоссе каждого типа.