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

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

Лемма о рукопожатиях (12 апреля 2014 года)

1.

На конференцию приехало 100 ученых. Во время церемонии открытия каждый пожал руку пяти другим. Сколько рукопожатий было совершено?

2.

Во дворе стоят 10 берёз и 6 фонарных столбов. Между ними натянуты бельевые вервеки так, что к каждому столбу привязано 7 веревок, а к каждой березе — 5. Сколько во дворе бельевых веревок?

3.

В некотором государстве 100 городов, из которых выходит по 3 дороги, и 100 городов, из которых выходит по 4 дороги. Сколько дорог всего?

4.

Сколько рёбер в полном графе с 10 вершинами?

5.

Докажите, что число рёбер в графе равно полусумме степеней его вершин.

6.

Можно ли 21 компьютер соединить проводами так, чтобы каждый был соединён с 11 другими?

7.

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

8.

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

9.

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

10.

В стране 2013 городов и сёл. Из столицы выходит 25 дорог, из села Полоскунова выходит всего одна дорога, а из всех остальных населенных пунктов — по 20 дорог. Енот хочет добраться от Полоскунова до столицы. Справится ли енот?

11.

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

12.

Можно ли все рёбра полного графа с 55 вершинами раскрасить в 54 цвета таким образом, чтобы все рёбра, выходящие из одной вершины, были разного цвета?

13.

В стране Оз есть много городов, некоторые из которых соединены дорогами. Каждая из дорог вымощена либо жёлтым кирпичом, либо красным, либо зелёным. Известно, что из Изумрудного города выходит ровно одна дорога, а из всех остальных городов — по три дороги. Докажите, что в стране Оз есть город, из которого выходят две дороги одного цвета.