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

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

Руководитель Дмитрий Владимирович Трущин
2013/2014 учебный год

Лемма о рукопожатиях (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.
В стране Оз есть много городов, некоторые из которых соединены дорогами. Каждая из дорог вымощена либо жёлтым кирпичом, либо красным, либо зелёным. Известно, что из Изумрудного города выходит ровно одна дорога, а из всех остальных городов — по три дороги. Докажите, что в стране Оз есть город, из которого выходят две дороги одного цвета.