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

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

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

Версия для печати

Занятие 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-угольника, а остальные — в форме шестиугольников?

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