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

Кружок 9-11 классов

Графы 1.2

1.

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

2.

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

3.

Двое по очереди проводят диагонали выпуклого 20-угольника. Запрещается проводить диагонали, имеющие общие точки (даже вершины) с уже проведёнными. Проигрывает тот, кто не может сделать ход. Кто из соперников имеет выигрышную стратегию?

4.

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

5.

На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Чему равно наибольшее число знакомств, которое могло быть среди участвовавших во встрече?

6.

В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из N авиакомпаний, причем из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из любого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт N−1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из любого города можно долететь до любого другого.

7.

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

8.

Докажите, что

а)

если в графе есть нечетная вершина (из которой выходит нечетное число ребер), то в нем нет пути, проходящего по всем ребрам по одному разу и возвращающегося в исходную вершину;

б)

если таких вершин нет, то такой путь обязательно есть.

Hint

Hint. Используйте индукцию; не исключено, что проще сначала решить следующий пункт.

в)

А что можно сказать про пути, проходящие по одному разу по всем ребрам, но не возвращающиеся в исходную вершину.

9.

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

10.

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