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

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

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

1.

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

2.

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

3.

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

4.

а)

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

б)

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

в)

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

5.

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

6.

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

7.

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

8.

а)

В классе каждый мальчик дружит с тремя девочками, а каждая девочка — с пятью мальчиками. Известно, 17 учеников этого класса любят играть в матбой и что в классе 15 парт. Сколько всего ребят в классе?

б)

В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с четырьмя мальчиками. Докажите, что число школьников в классе делится на 7.

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

9.

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

10.

В стране А города соединены авиалиниями. Из столицы выходит 777 линий, из города В – 1 линия, из остальных – по 20. Докажите, что из столицы можно добраться до В авиатранспортом (возможно, с пересадками).