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

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

Занятие 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.

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