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

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

Занятие 13 (12 февраля 2011 года)

Графы

1.

Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

2.

Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

3.

В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

4.

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

5.

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

6.

В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

7.

У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей?

8.

В школе 1717 учеников. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.

9.

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