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

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

Руководитель Степан Львович Кузнецов
2015/2016 учебный год
Группа К (старший преподаватель Л. Н. Колотова)

Занятие 8 (14 ноября 2015 года). Графы

1.
10 подружек договорились в «День подружек» обменяться поздравлениями. Каждая отправила по одной SMS-ке пяти подругам. Докажите, что какие-то две из них обменялись SMS-ками друг с другом.
2.
В верхних углах доски 3×3 стоят черные кони, а в нижних — белые. Как разместить коней одного цвета в противоположных клетках доски и сколько ходов для этого необходимо?
3.
ЛМШонок Петя сделал на окно сетку от комаров, в которой оказалось ровно 100 узелков, и любые два узелка соединены ниточкой. Сколько всего ниточек использовал Петя?
4.
В стране 17 городов, каждый из которых соединен дорогами не меньше, чем с 8-ю другими городами этой страны. Докажите, что в внутри страны можно доехать из любого города в любой другой.
5.
Сытый марсианский кот Васька поймал 6 марсианских треххвостых мышек и связал их хвостами так, что свободных хвостов не осталось. Сколько узелков ему пришлось завязать? Васька поймал еще одну мышку и решил, развязав некоторые из узелков, связать эту мышку со всеми остальными. Сможет ли он это сделать так, чтобы по-прежнему не было свободных хвостов?
6.
В графе каждая вершина покрашена в синий или зеленый цвет. При этом каждая синяя вершина связана с пятью синими и десятью зелеными, а каждая зеленая с девятью синими и шестью зелеными. Каких вершин больше – синих или зеленых?
7.
Есть 15 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 15 написаны по два раза. Доказать, что все карточки можно выложить на стол так, чтобы все числа сверху были различны.
8.
Нарисуйте в тетради 9 отрезков (какой хотите длины, толщины и цвета) так, чтобы каждый отрезок пересекался ровно с тремя другими.
9.
Можно ли на окружности расположить числа 0, 1, 2, …, 9 так, чтобы любые два соседних числа отличались на 3, 4 или 5?

Для самостоятельного решения

1.
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
2.
В трёх вершинах правильного пятиугольника расположили по фишке. Разрешается двигать их по диагонали на свободное место. Можно ли таким образом добиться, чтобы одна из фишек вернулась на первоначальное место, а две другие поменялись местами?