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

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

Занятие 21 (03.03.2012). Графы

1.

Между планетами Солнечной системы введено космическое сообщение. Ракеты летают по маршрутам Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс, Марс — Уран. Можно ли добраться с Земли до Марса?

Ответ Решение

Ответ. Нет, нельзя.

Решение. Нарисуем, как связаны планеты.

Теперь ясно, что от Земли до Марса добраться нельзя.

2.

На День рождения к Андрею пришли Вася, Глеб, Даша, Митя, Петя, Соня и Тимур. Покажите, как восьмерых ребят можно рассадить за круглый стол, чтобы у любых двух, сидящих рядом, в именах встречались одинаковые буквы.

Ответ

Ответ. Можно посадить детей так: Вася → Даша → Андрей → Глеб → Петя → Тимур → Митя → Соня.

3.

В пяти корзинах лежат яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах А и В; яблоки второго сорта — в корзинах Б, В и Д; в корзинах Б, Г и Д имеются яблоки пятого сорта; в корзине Г есть к тому же яблоки четвёртого сорта, а в корзине А — третьего. Можно ли дать каждой корзине номер так, чтобы в корзине №1 было хотя бы одно яблоко первого сорта, в корзине №2 — второго и т.д.?

Ответ Решение

Ответ. Да, можно.

Решение. Поскольку яблоки третьего сорта есть только в корзине А, то она будет третьей. Аналогично, Г будет четвертой корзиной. Пусть также В будет первой, Б — второй и Д — пятой. Т.е., порядок будет ВБАГД.

4.

а)

На шахматной доске 3×3 стоят два чёрных и два белых коня. Белые кони стоят в левом верхнем и правом верхнем углах доски, а чёрные — в левом нижнем и правом нижнем углах. Можно ли сделать несколько ходов конями так, чтобы они поменялись местами?

б)

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

5.

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

Ответ Решение

Ответ. Да, могло.

Решение. Пусть город — три улицы, выходящих из одной площади. Тогда начав с площади последовательно будем обходить каждую улицу туда-обратно. Очевидно, что улицы такого города нельзя пройти по разу.

6.

а)

В графе с 8 вершинами любые две вершины соединены ребром. Сколько всего рёбер в этом графе?

б)

Тот же вопрос, если в графе не 8, а n вершин.

Ответ Решение

Ответ. а) (8·7)⁄2 = 28; б) n·(n − 1)⁄2.

Решение. Из каждой вершины выходит ровно n − 1 ребро, причем каждое ребро соединяет две вершины. Поскольку всего вершин n, то всего ребер n(n − 1)⁄2.

7.

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

Решение

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

8.

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

Ответ

Ответ. 870.