графы

Задача 1

Школьник сказал своему приятелю Вите Иванову: -- У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками... -- Не может этого быть,  — сразу ответил Витя Иванов, победитель математической олимпиады. Почему он так решил?

Решение:

Представим себе, что между каждыми двумя друзьями протянута ниточка. Тогда каждый из 35 учеников будет держать в руке 11 концов ниточек, и значит, всего у протянутых ниточек будет 1135 = 385 концов. Но общее число не может быть нечётным, так как у каждой ниточки 2 конца.

Задача 2

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

Решение:

Каждая мышка за одну ночь может побывать на складе с тремя другими мышками. Чтобы побывать на складе с каждой из 23 других мышек по одному разу, ей необходимо 23/3 ночей. Но число 23 не делится нацело на три. Поэтому такая ситуация невозможна.

Ответ: Нет, такого быть не может.

Задача 3

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

Решение:

Обозначим через Р количество пар знакомых людей, а через Т - количество троек попарно знакомых людей (т.е. количество троек людей, в которых каждые двое знакомы между собой). По условию у каждой пары знакомых людей есть ровно 5 общих знакомых, это означает, что каждая из Р пар знакомых людей входит ровно в 5 троек попарно знакомых людей. С другой стороны, в каждую из Т троек попарно знакомых людей входит ровно 3 пары знакомых людей. Сделанные замечания позволяют написать равенство: 5Р=3Т. Поскольку 3 и 5 - взаимно простые числа, Р делится на 3, что и требовалось доказать.

Задача 4

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

Решение:

Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины.

Задача 5

Верно ли, что два графа изоморфны, если

а) у них по 10 вершин, степень каждой из которых равна 9?

б) у них по 8 вершин, степень каждой из которых равна 3?

в) они связны, без циклов и содержат по 6 ребер?

Решение:

а) Верно. Каждая вершина соединена с каждой.

б) Нет

в) Нет

Задача 6

Каждое из ребер полного графа с 6 вершинами покрашено в один из двух цветов. Докажите, что есть три вершины, все ребра между которыми - одного цвета.

Решение:

Среди рёбер, выходящих из данной вершины, можно найти три ребра одного цвета. Среди трех вершин, в которые ведут эти рёбра, или какие-то две соединены ребром того же цвета, тогда они вместе с выбранной нами исходно образуют нужную тройку, либо все рёбра между ними одноцветны.

Задача 7

В секретной службе работают n агентов - 001,002,...,007,...,n. Первый агент следит за тем, кто следит за вторым, второй - за тем, кто следит за третьим, и т.д., n-ый - за тем, кто следит за первым. Докажите, что n - нечетное число.

Решение:

Обозначим агентов точками и проведем стрелку от агента A к агенту B в том случае, когда A следит за B. Поскольку каждый агент следит ровно за одним другим, мы получим некоторый цикл (или несколько циклов) из стрелок. Согласно условию, если начать движение по стрелкам, начиная с первого агента и проходя за один раз по двум стрелкам, мы встретим подряд всех агентов с номерами 2, 3, ... , n, и в конце снова придем к первому агенту (это в частности означает, что цикл единственный). Легко видеть, что в случае четного числа агентов такой обход стрелок невозможен.

Задача 8

Как соединить 50 городов наименьшим числом авиалиний так, чтобы из любого города можно было попасть в любой, сделав не более двух пересадок?

Решение:

Выделим один город и соединим его авиалинией с каждым из остальных 49 городов. Для этого потребуется 49 авиалиний. Покажем, что меньшим числом авиалиний обойтись нельзя. А именно, докажем индукцией по n, что связный граф с n вершинами содержит не менее n - 1 рёбер. При n2 это утверждение очевидно. Возьмём связный граф с nвершинами и будем последовательно уничтожать его рёбра до тех пор, пока он не перестанет быть связным. Пусть до уничтожения k-го по счёту ребра (k1) граф был связным, а после его уничтожения он распался на два графа с n₁ и n₂ вершинами. Эти графы связны, поэтому по предположению индукции они имеют, соответственно, не менее n₁ - 1 и n₂ - 1 рёбер. Следовательно, исходный граф имеет не менее k + (n₁ - 1) + (n₂ - 1) = k + n - 2n - 1 рёбер.

Задача 9

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

Решение:

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

Задача 10

В классе 20 учеников, причем каждый дружит не менее, чем с 14-ю другими. Можно ли утверждать, что найдутся четыре ученика, которые все дружат между собой?

Решение:

Соберем весь класс в одной комнате. Рассмотрим некоторого человека А. Пусть теперь из комнаты выйдут все ученики, которые не дружат с А. По условию таких не более пяти человек. Поэтому в комнате осталось по крайней мере 15 учеников. Далее, выберем из оставшихся в комнате ученика Б, отличного от А. Пусть из комнаты выйдут все ученики, которые не дружат с Б. После этого в комнате осталось не меньше 10 учеников. Наконец, выберем из оставшихся в комнате ученика В, отличного от А и от Б. Пусть из комнаты выйдут все ученики, которые не дружат с В. После этого в комнате осталось не меньше 5 учеников. Эти 5 учеников - это А, Б, В (А, Б, В дружат между собой), и еще 2 ученика Г и Д, которые дружат с А, Б, В. Итак, искомая четверка учеников - это, например, А, Б, В, Г.

Задача 11

Тетрадный лист раскрасили в 23 цвета по клеткам. Пара цветов называется хорошей, если существует две соседние клетки, закрашенные этими цветами. 
Каково минимальное число хороших пар?  

Решение:

Нарисуем граф с 23 вершинами (цветами) и соединим рёбрами вершины, соответствующие хорошим парам.
Докажем, что этот граф связан. Построим путь от вершины A до вершины B по рёбрам графа. Возьмём некоторую клетку , окрашенную в цвет A, и некоторую клетку , окрашенную в цвет B. Построим "цепочку" клеток, соединяющих  с  (например, из клеток, которые пересекает отрезок, соединяющий центры клеток  и ). Каждым двум разноцветным соседним клеткам этой "цепочки" соответствует хорошая пара цветов, т. е. ребро нашего графа.
Поскольку граф связан, в нём не менее 22 рёбер. Приведём пример раскраски в 23 цвета с 22 хорошими парами цветов. Покрасим 22 несоседние клетки в 22 цвета, а оставшиеся клетки — в 23-й цвет.

Ответ: 22 хорошие пары.

Задача 12

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

Ответ: 4

Задача 13

В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трех друзей.

Решение:

Общее число способов выбрать компанию из 3 человек равно C₁₀³ = 120. Каждая ссора разрушает не более 8 таких компаний, поэтому число разрушенных компаний не больше 8 ^. 14 = 112. Значит осталось по крайней мере 8 дружных компаний. 

Задача 14

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

Решение:

Предположим противное. Тогда для каждого числа от 68 до 101 есть ровно три человека, имеющие такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Задача 15

Докажите, что среди 50 человек найдутся двое, у которых чётное число общих знакомых (быть может, 0) среди остальных 48 человек.  

Решение:

Предполагается, что знакомство симметрично, т. е. если А знаком с Б, то Б знаком с А (будем писать в таком случае А  Б). Ситуацию будем изображать графом, вершины которого — люди, а рёбрами соединены знакомые. Допустим противное, т. е. предположим, что любые два человека имеют нечётное число общих знакомых, т. е. любые две вершины графа соединены нечётным числом двузвенных ломаных.
Пусть a — одна из вершин графа, A — множество вершин, связанных с ней ребром. Допустим, что в A нечётное число вершин; обозначим их a₁, a₂, ..., a_i (i нечётно). Каждаяa_j связана с a нечётным числом двузвенных ломаных, рассмотрим множество средних вершин этих ломаных; их число обозначим через f_j. Все f_j по предположению нечётны. Следовательно, f_j также нечётна. В этой сумме каждая вершина из A сосчитана столько раз, сколько отрезков подходит к ней от других вершин A. Поэтому сумма равна общему числу концов этих отрезков, т. е. чётна. Противоречие.
Докажем теперь основное утверждение. Обозначим через B множество вершин, не связанных ребром с a. B содержит нечётное число вершин (всего вершин 50, вычитаем чётное число вершин в A и ещё одну вершину a). Число двузвенных цепочек вида a  a_j  b (b  B) нечётно, так как элементов b нечётное число и троек a  a_j  b при данном b (и данном a) также нечётное число. С другой стороны, каждая a_j входит в чётное число таких цепочек, так как данная a_j связана отрезком с нечётным числом вершин в A (иначе a соединяется с a_j чётным числом двухзвенных ломаных), с вершиной a, и следовательно, с чётным числом вершин в B. Таким образом, получается, что число цепочек вида a  a_j  b чётно. Это противоречие доказывает утверждение задачи.

Задача 16

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

Решение:

Разобьем каждую улицу на две полуулицы и сосчитаем их число. Если n – число перекрестков в городе, а c_i – число внешних дорог цвета i , то числа полуулиц каждого цвета будут n+c1 , n+c2 , n+c3 . Все эти числа четные, следовательно, четность чисел c1 , c2 , c3 одинакова. По условию, c1+c2+c3=3 . Значит, c1=c2=c3=1 .

Задача 17

Каждое из ребер полного графа с 9 вершинами покрашено в синий или красный цвет. Докажите, что либо есть четыре вершины, все ребра между которыми - синие, либо есть три вершины, все ребра между которыми - красные.

Решение:

Пусть есть вершина, из которой выходит 6 синих ребер. Тогда воспользуемся результатом задачи 37. Пусть есть вершина, из которой выходит не более 4 синих ребер (из всех 9-ти вершин не может выходить по 5 синих ребер). Тогда из нее выходит по крайней мере 4 красных ребра.

Советуем прорешать начинающей и средней группам

Задача 1

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?

Задача 2

У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

Задача 3

Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?

Задача 4

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

Задача 5

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

Задача 6

В классе 20 учеников, причем каждый дружит не менее, чем с 14-ю другими. Можно ли утверждать, что найдутся четыре ученика, которые все дружат между собой?

Задача 7

30 команд сыграли турнир по олимпийской системе. Сколько всего было сыграно матчей?

Задача 8

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

Задача 9

Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. 

Сколько друзей у Пети? (Укажите все решения.)

Задача 10

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

Задача 11

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

Задача 12

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