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

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

Руководитель Степан Львович Кузнецов
2016/2017 учебный год
Группа А

Занятие 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. Докажите, что из столицы можно добраться до В авиатранспортом (возможно, с пересадками).

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS