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

Кружок 10 класса

Графы (10.10.2009)

1.

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

2.

В некотором государстве 99 городов, некоторые пары городов соединены дорогами длиной в 1, 3 или 5 вёрст, причём от каждого города до каждого по этим дорогам можно добраться ровно одним способом. Из каждого города в каждый другой отправились гонцы с важным донесением. Докажите, что суммарное расстояние, пройденное гонцами, делится на 4.

3.

а)

Квадрат со стороной 10 разделён отрезками на 100 квадратиков 1×1. Точки пересечения полученных отрезков отмечены. Какое наибольшее количество маленьких отрезков, соединяющих соседние точки, можно стереть, чтобы полученная фигура осталась связной?

б)

Куб со стороной n (n ≥ 3) разбит перегородками на единичные кубики. Какое наименьшее число перегородок между единичными кубиками нужно удалить, чтобы из любого кубика можно было добраться до границы большого куба?

4.

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

5.

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

6.

В стране несколько городов, некоторые пары из которых соединены беспосадочными рейсами одной из N авиакомпаний, причём из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из любого города можно долететь до любого другого (возможно с пересадками). Из-за финансового кризиса был закрыт N − 1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что попрежнему из любого города можно долететь до любого другого.

7.

В стране из каждого города выходит по 3 железные дороги. Две компании хотят их все приватизировать. Антимонопольный комитет требует, чтобы из каждого города выходили дороги обеих компаний. Докажите, что компании могут договориться между собой, чтобы требование Антимонопольного комитета было выполнено.