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

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

Занятие 13. При чём здесь граф?(18.02.2006)

1.

При дворе принца Лимона служили герцоги, графы и бароны. В начале правления принца придворных было 2006, но каждый день один из них убивал другого на дуэли, причем графы убивали только герцогов, герцоги — только баронов, а бароны — только графов. При этом никто не выиграл дуэль дважды. В конце концов остался в живых лишь граф Апельсин. Какой титул был у первого погибшего придворного?

Ответ Решение Комментарий

Ответ. Герцог.

Решение. Присвоим всем придворным номера. Номер 1 получит тот, кто погиб раньше всех, номер 2 — тот, кто погиб вторым, номер 3 — тот, кто погиб третьим, …, номер 2005 получит тот, кто погиб 2005—ым, то есть последним, а номер 2006 — граф Апельсин. 2005—ый был убит графом Апельсином, так как кроме него и графа Апельсина к тому времени никого больше не осталось. Значит, 2005—ый был герцогом, так как графы убивали только герцогов. После гибели 2004—ого остались только 2005—ый и граф Апельсин. Значит, 2004—ого убил кто—то из них. Но граф Апельсин это сделать не мог, так как он убил 2005—ого, а двоих не мог убить один и тот же человек. Значит, 2004—ого убил 2005—ый. Так как 2005—ый был герцогом, то 2004—ый был бароном. Аналогично можно установить, что 2003—его убил 2004—ый, значит, 2003—ий был графом.
Так как 2006 = 668 · 3 + 2, то, с помощью аналогичных рассуждений двигаясь по цепочке «граф — герцог — барон», мы пройдём её 668 раз целиком (это означает, что 3—ий был бароном), и ещё останется два шага. Тогда получается, что 2—ой был графом, а 1—ый, который был убит раньше всех, был герцогом.

Комментарий. Можно сказать так:

• если номер придворного даёт остаток 2 при делении на 3, то он был графом;
• если номер придворного даёт остаток 1 при делении на 3, то он был герцогом;
• а если номер придворного даёт остаток 0 при делении на 3, то есть делится на 3, то он был бароном.

Тогда можно сразу сказать, что погибший первым был герцогом, так как 1 даёт остаток 1 при делении на 3.

2.

В Таниной квартире есть восемь розеток, 21 тройник и неограниченное количество утюгов. Какое наибольшее число утюгов Таня может включить одновременно?

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

Ответ. 50 утюгов.

Решение. При подключении тройника используется один, но появляются три новых выхода, к которым можно подключать утюги. Таким образом, каждый тройник может добавить 3 — 1 = 2 свободных выхода. Первоначально было 8 розеток, то есть 8 выходов. Если подключить все тройники, которые есть, то количество свободных выходов станет равно 8 + 2 · 21 = 50. То есть можно подключить 50 утюгов, задействовав все средства, которые есть в наличии.

3.

В графе n вершин, и каждая соединена с каждой. Сколько рёбер в графе?

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

Ответ. n(n − 1)⁄2 рёбер.

Решение.
I способ.
Из каждой из n вершин выходит n − 1 ребро (степень каждой вершины равна n − 1). Сумма степеней всех вершин будет n·(n − 1). Так как каждое ребро выходит ровно из двух вершин, каждое ребро мы посчитали дважды. Значит, на самом деле количество рёбер в два раза меньше.
II способ.
Будем считать рёбра. Возьмём любую вершину графа. Из неё выходит (n − 1) ребро. Возьмём вторую вершину. Одно ребро соединяет её с первой, и мы его уже сосчитали. Осталось добавить (n − 2) ребра. Аналогично, из третьей вершины выходит (n − 3) «новых» ребра, из четвёртой — (n − 4), …, из (n − 1)-ой будет выходить n − (n − 1) = 1 «новое» ребро, из n—ой вершины — n − n = 0 «новых» рёбер. Получается, что всего рёбер в этом графе (n − 1) + (n − 2) + … + 1 + 0. Сумму этих чисел можно найти так: складываем первое число с последним, второе с предпоследним, и т.д.

4.

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

Решение

Решение. Составим граф, в котором вершинами будут люди, а рёбрами — сделанные ими рукопожатия: каждую пару вершин будет соединять столько рёбер, сколько рукопожатий сделали соответствующие люди. Если бы число людей, сделавших нечётное число рукопожатий, было нечётным, то тогда в нашем графе было бы нечётное число вершин, из которых выходит нечётное число рёбер, то есть нечётное число вершин нечётной степени. Тогда сумма степеней всех вершин была бы нечётным числом, так как сумма любого числа чётных чисел чётна, а сумма нечётного числа нечётных чисел нечётна. Но в решении предыдущей задачи было доказано, что сумма степеней всех вершин графа всегда чётна. Получаем противоречие. Значит, число людей, сделавших нечётное число рукопожатий, чётно.

5.

В графе каждая вершина покрашена в синий или зеленый цвет. При этом каждая синяя вершина связана с пятью синими и десятью зелеными, а каждая зеленая с девятью синими и шестью зелеными. Каких вершин больше — синих или зеленых?

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

Ответ. Зелёных вершин больше.

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

6.

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

7.

В городе проводилось совещание врачей. От каждой поликлиники на совещание было приглашено по пять врачей. Оказалось, что каждый из приглашенных работал в двух поликлиниках, поэтому на совещании представлял обе поликлиники. Кроме того, для любых двух поликлиник города среди участников совещания найдется врач, который в них работает. Сколько в городе поликлиник и сколько врачей принимало участие в совещании?

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

Ответ. 2 поликлиники и 5 врачей; 4 поликлиники и 10 врачей; 6 поликлиник и 15 врачей.

Решение.
Построим граф, в котором вершины будут обозначать поликлиники, а рёбра — врачей: любые две вершины поликлиники будут соединять столько рёбер, сколько врачей, из тех, кто приглашён на совещание, работает и в той, и в другой поликлинике.
Из условия задачи следует, что из каждой вершины выходит по 5 рёбер. Так как для любых двух поликлиник среди участников совещания найдется врач, который в них работает, то любые две вершины соединены хотя бы одним ребром. Из этого следует, что в городе не могло быть больше 6 поликлиник, так как иначе, из каждой вершины графа должно было бы выходить не менее 6 рёбер.
Обозначим количество поликлиник p, а количество врачей v. Тогда количество рёбер в графе v = 5p⁄2 (см. задачу 3). Тогда 5p делится на 2, а так как 2 и 5 — взаимно просты, то из этого следует, что p делится на 2, то есть p — чётное.
Поэтому возможные значения для p: 2, 4, 6. Для каждого из этих значений p несложно построить примеры, показывающие, что такие значения возможны.

• p = 2: две вершины, соединённые пятью рёбрами;
• p = 4: четыре вершины, любые две из которых соединены двумя рёбрами, кроме пар, составленных, из первой и второй, третьей и четвёртой вершин, которые соединены одним ребром;
• p = 6: шесть вершин, любые две из которых соединены одним ребром.

Из соотношения v = 5p⁄2 для каждого из трёх значений p можно найти соответствующее значение v.

8.

На окружности отмечены 7 красных и 5 синих точек. Каких треугольников с вершинами в этих точках больше: одноцветных или разноцветных? На сколько?

Ответ

Ответ. Разноцветных треугольников больше на 135.