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

Кружок 9-11 классов

Руководители Фируза Исамитдиновна Мамедова и Александра Ефремовна Подгайц
2012/2013 учебный год

Графы 2

1.
а)
В Тридевятом царстве 100 городов. Каждый соединен с каждым. Сколько всего дорог в царстве?
б)
А если из каждого города выходит по 4 дороги, то сколько в этом случае дорог в царстве?
2.
Можно ли нарисовать 9 отрезков так, чтоб каждый пересекался ровно с 3 другими?
3.
В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?
4.
В стране 15 городов, из каждого выходит по крайней мере по 7 дорог. Докажите, что из каждого города можно добраться в каждый (двигаясь только по этим дорогам). Может ли случиться такое, что из каждого города выходит ровно по 7 дорог?
5.
Дима, приехав из Врунляндии, рассказал, что там есть несколько озер, соединенных между собой реками. Из каждого озера вытекают три реки, и в каждое озеро впадают четыре реки. Докажите, что он ошибается.
6.
На рисунке изображена схема мостов города Кенигсберга. Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?
7.
Схема городов и авиалиний в некотором государстве изображена на рисунке. Можно ли облететь все города, побывав в каждом из них по одному разу?
8.
В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого
9.
В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?
10.
Имеются две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть «двойник» в Зазеркалье, и наоборот. Однако если в Обычной стране какие-то два города соединены железной дорогой, то в Зазеркалье эти города не соединены, а любые два несоединённых в Обычной стране города обязательно соединены железной дорогой в Зазеркалье. В Обычной стране девочка Алиса не может проехать из города А в город Б, сделав менее двух пересадок. Докажите, что в Зазеркалье Алиса сможет проехать из любого города в любой другой, сделав не более двух пересадок.