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

Кружок 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 железные дороги. Две компании хотят их все приватизировать. Антимонопольный комитет требует, чтобы из каждого города выходили дороги обеих компаний. Докажите, что компании могут договориться между собой, чтобы требование Антимонопольного комитета было выполнено.