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

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

Занятие 15. И снова графы(4.03.2006)

1.

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

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

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

Решение. Предположим, что это сделать можно. Построим граф, в котором вершины будут обозначать шары, и две вершины будут соединены ребром, если соответствующие шары касаются. Тогда в полученном графе будет пять вершин, и все они будут иметь степень три. Но этого быть не может, так как в графе не может быть нечётное число вершин нечётной степени (см. решение задачи №4 из занятия №13). Получаем противоречие. Значит, расположить пять шаров указанным образом нельзя.

2.

На дискотеке каждый мальчик танцевал ровно с десятью девочками, а каждая девочка — ровно с девятью мальчиками. Кого было больше: мальчиков или девочек?

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

Ответ. Больше было девочек.

Решение. Пусть мальчиков было m, а девочек d. Построим граф, в котором вершины будут двух цветов: синие будут обозначать мальчиков, а красные — девочек. Рёбра будут соединять только вершины разных цветов, причём в том и только в том случае, если соответствующие мальчик и девочка танцевали на дискотеке. Так как из каждой синей вершины выходит ровно 10 рёбер, а у каждого ребра есть ровно один синий конец, то отсюда следует, что количество рёбер в нашем графе равно 10m. Из аналогичных соображений можно получить, что оно также равно 9d. Значит, 10m = 9d или m=0,9d. Следовательно, девочек было больше.

3.

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

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

Ответ. Не могут.

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

4.

Существует ли граф, степени вершин которого равны:
а) 9, 8, 7, 6, 5, 4, 3, 2, 1;
б) 5, 5, 4, 4, 4, 3, 2, 2, 1;
в) 9, 8, 8, 7, 6, 5, 4, 2, 1;
г) 9, 8, 5, 4, 3, 3, 2, 2, 1;
д) 2, 1, 1, 1, 1, 1, 1, 0, 0?

Решение

Решение. В каждом из пунктов граф должен содержать 9 вершин, поэтому степень никакой из вершин не может быть больше 8 (максимальное значение, равное 8, достигается, если вершина соединена со всеми остальными). Из этого следует, что в пунктах а), в) и г) ответ — нет. Для пунктов б) и д) можно построить примеры графов, удовлетворяющих указанным условиям.

5.

Среди 40 внешне одинаковых монет 2 фальшивые — они легче, чем остальные и весят одинаково. Как за два взвешивания на чашечных весах без стрелок и гирек определить 20 настоящих монет?

Решение

Решение. Сначала кладём на каждую из чашек весов по 10 монет. Это будет первое взвешивание.
Пусть одна из чашек перевесила. Тогда все монеты на ней — настоящие. (Иначе бы на «лёгкой» чашке было не менее двух фальшивыйх монет, что невозможно.) А среди монет на «лёгкой» чашке есть не меньше одной фальшивой, отложим эту кучку в сторону.
Возьмём ещё десять монет и сравним их вес с настоящими. Это будет второе взвешивание. Если весы уравновесились, то мы нашли двадцать настоящих монет. Если весы не уравновесились, значит, среди новых десяти монет есть ещё одна фальшивая. Но это значит, что среди последних десяти монет фальшивых нет. Так что и в этом случае мы нашли двадцать настоящих монет.
Теперь рассмотрим случай, когда при первом взвешивании весы показывают равновесие. В этом случае среди монет, которые находятся на весах, либо нет фальшивых, либо есть по одной на каждой чашке. Уберём монеты с одной из чашек и вместо них положим 10 других, которые не участвовали в первом взвешивании. Если в «старой» кучке есть фальшивая монета, то в «новой» кучке фальшивых монет нет, так как вторая фальшивая монета была снята с весов перед вторым взвешиванием. В этом случае «новая» кучка перевесит. Если в «старой» кучке нет фальшивых монет, то при втором взвешивании весы либо покажут равенство, либо «старая» кучка перевесит. Таким образом, из результатов второго взвешивания мы можем узнать, где находятся обе фальшивые монеты: среди 20 монет, которые участвовали в первом взвешивании, или среди 20 других.

6.

Превратите зубчатый квадрат в обыкновенный, разрезав его на пять частей.

Решение

Решение.

7.

На столе лежит 5 коробочек. В некоторых коробочках лежит по пять коробочек, в некоторых из них тоже лежит по пять коробочек, и так далее, а пустых коробочек получилось всего 25. Сколько всего коробочек?

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

Ответ. 30 коробочек.

Решение. Пусть у нас есть 5 пустых коробочек. В некоторые из них мы можем положить по 5 пустых коробочек. В некоторые из новых коробочек также можно положить по 5 пустых и т. д. Действуя так, можно получить любую возможную ситуацию, в том числе и любую из тех, которые удовлетворяют условию задачи.
Если в пустую коробочку положить 5 других, то общее число коробочек увеличится на 5, а количество пустых увеличится на 4 (так как появляется 5 новых пустых коробочек, а исходная перестаёт быть пустой: 5 − 1 = 4). В начале было 5 пустых коробочек, а в конце их стало 25. Количество пустых коробочек увеличилось на 20. Значит, указанную операцию с добавлением коробочек проделали 20 : 4 = 5 раз, так как за каждую такую операцию количество пустых коробочек увеличивается на 4. Тогда общее их количество должно было увеличиться на 5 · 5 = 25, то есть их стало 5 + 25 = 30.

8.

В марсианском метро 101 станция и 5000 перегонов между станциями. Докажите, что можно добраться с любой станции до любой другой.

Решение

Решение. Всего между 101 станцией может быть не более 101·100⁄2=5050 перегонов. Если с какой-то станции нельзя даже с пересадками добраться до какой-то другой, то все станции можно разделить на две группы так, что ни с одной станции первой группы нельзя добраться ни до какой станции второй группы. (Это будет наглядно видно, если составить граф, в котором вершины обозначают станции, а рёбра — перегоны.)
Так как всего станций 101, то в одной из групп не менее 51 станции. Возьмём любую станцию из другой группы. Она не соединена перегоном ни с одной станцией первой группы (в которой не менее 51 станцией). Тогда всего перегонов между станциями не может быть больше 5050 − 51 = 4999 < 5000. Таким образом, если с какой-то станции нельзя добраться до какой-то другой, то получается противоречие с условием задачи. Значит, это не так, то есть, с любой станции можно добраться до любой другой.

9.

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

Решение

Решение. Рассмотрим граф, в котором n вершин. Степень любой из его вершин может быть равна одному из чисел 0, 1, 2, …, n − 1. Всего n возможных вариантов. Так как вершин тоже n, то для того, чтобы все вершины имели попарно разные степени необходимо, чтобы все эти варианты достигались: то есть, чтобы в графе была вершина степени 0, была вершина степени 1, …, была вершина степени n − 1. Но этого быть не может, так как если вершина имеет степень 0, то это означает, что она не соединена ни с одной другой вершиной, а если вершина имеет степень n − 1, то это означает, что она соединена со всеми остальными. То есть, варианты 0 и n – 1 одновременно достигаться не могут.