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

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

Занятие 7 (19 ноября 2016 года). Графы 2

1.

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

2.

Степенью вершины графа называется количество рёбер, исходящих из этой вершины. В графе G восемь вершины, петель и кратных рёбер нет. Могут ли степени вершин графа G быть равны:

а)

8, 6, 5, 4, 4, 3, 2, 2?

б)

7, 7, 6, 5, 4, 2, 2, 1?

в)

7, 6, 5, 4, 4, 3, 2, 1?

г)

6, 6, 6, 5, 5, 3, 2, 2?

3.

Можно ли расположить на плоскости

а)

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

б)

6 точек и соединить их непересекающимися отрезками так, чтобы из каждой точки выходило ровно 4 отрезка?

4.

В парламенте Острова Рыцарей и Лжецов каждый депутат сказал некоторым другим депутатам, что те лжецы. Докажите, что парламент можно разделить на две палаты так, что никакой депутат не говорил другому депутату из той же палаты, что тот лжец.

5.

а)

Из какого наименьшего числа кусков проволоки можно спаять каркас куба? (Разрезать проволоку не разрешается.)

б)

Какой наибольшей длины кусок проволоки можно вырезать из этого каркаса? (Длина ребра куба равна 1 см.)

6.

Выпишите в ряд цифры от 1 до 9 (каждую ровно один раз) так, чтобы каждые две подряд идущие цифры давали бы двузначное число, делящееся на 7 или на 13.

Дополнительные задачи

7.

В поселке 20 жительниц. 1 марта одна из них узнала интересную новость и сообщила ее всем своим подругам. 2 марта те сообщили новость всем своим подругам, и так далее. Может ли так случиться, что:

а)

15 марта еще не все жительницы будут знать новость, а 18 марта уже все?

б)

25 марта еще не все жительницы будут знать новость, а 28 марта уже все?

8.

Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.

9.

В графе каждая вершина – синяя или зелёная. При этом каждая синяя вершина связана с 5 синими и 10 зелёными, а каждая зелёная – с 9 синими и 6 зелёными. Каких вершин больше – синих или зелёных?