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

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

Задание 5 - Рыцари, Бароны, Виконты и Графы

Вспомнить

0.

На острове стоит 10 замков. Некоторые из них соединены дорогами. Известно, что у Рыцаря дороги уходят к замкам Барона и Виконта, у Маркиза к Графу и Герцогу, Князя – Принцу и Бакалавру. Также соединены замки Басилевса и Бакалавра, Барона и Герцога, Басилевса и Принца, Герцога и Виконта. Больше дорог на острове нет. Рыцарь посылает сообщение из своего замка до Бакалавра. Дойдет ли оно?

1.

Докажите, что число Рыцарей, когда-либо живших на земле и сделавших нечетное число рукопожатий – четно!

2.

Докажите, что в любой компании Баронов найдутся два Барона, у которых поровну знакомых в этой компании.

Изучить

3.

Степень каждой вершины связного графа не меньше 100. Одно ребро выкинули. Может ли граф оказаться несвязным?

4.

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

5.

В Метрополитене 12 станций метро, связанных 56 перегонами(каждые две станции соединены не более чем одним перегоном). Докажите, что Метрополитен связен.

Последнее

6.

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

7.

(Задача Эйлера о кенигсбергских мостах)

На реке два острова – Большой и Малый. Острова и берега соединены мостами, как показано на рисунке. Докажите, что нельзя пройти по всем мостам, побывав на каждом ровно один раз.

8.

Можно ли из проволоки длины 12 см сложить каркас кубика с ребром 1 см?

9.

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