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

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

Занятие 4 (22 октября 2016 года). Графы

1.

Волшебная страна Фарг почти вся состоит из непреодолимых гор и рек. В ней есть шесть городов: А, Б, В, Г, Д и Е. Известно, что из А проложены дороги в Б и Г, из Б — в А, Г и Д, из В — в Г и Е, из Г — в В и Д, из Д — в Б и Г, из Е — только в В. Все остальные пути непроходимы.

а)

Известно, что дороги в стране Фарг не пересекаются. Нарисуйте схематическую карту страны.

б)

Может ли житель города А попасть в город Д, если ему нельзя проходить через Г?

в)

Сможет ли он при тех же условиях попасть в город Е?

2.

На день рождения к Андрею пришли Вася, Глеб, Даша, Митя, Петя, Соня и Тимур. Покажите, как восьмерых ребят можно рассадить за круглый стол, чтобы у любых двух, сидящих рядом, в именах встречались одинаковые буквы.

3.

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

4.

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

5.

а)

Можно ли придумать пять таких слов, чтобы каждое имело хотя бы одну общую букву ровно с тремя другими?

б)

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

в)

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

6.

В стране 17 городов, каждый из которых соединен дорогами не меньше, чем с 8 другими городами этой страны. Докажите, что в внутри страны можно доехать из любого города в любой другой.

7.

Страна называется пятёрочной, если в ней каждый город соединён авиалиниями ровно с пятью другими городами (международных рейсов нет).

а)

Нарисуйте схему авиалиний для пятёрочной страны из 10 городов.

б)

Сколько авиалиний в пятёрочной стране из 50 городов?

в)

Может ли существовать пятёрочная страна, в которой ровно 46 авиалиний?

Дополнительные задачи

8.

В графе каждая вершина — синяя или зелёная. При этом каждая синяя вершина связана с 5 синими и 10 зелёными, а каждая зелёная — с 9 синими и 6 зелёными. Каких вершин больше — синих или зелёных?

9.

На дискотеку пришли а) 10 девушек и 9 юношей; б) 11 девушек и 10 юношей. Могло ли быть так, что все девушки знакомы с различным числом юношей, а все юноши – с одинаковым числом девушек?

10.

От куска сыра, имеющего форму куба, прямыми разрезами отрезают части. Может ли оставшийся кусок иметь одну грань в форме 13-угольника, а остальные — в форме шестиугольников?