Все задачи

Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75).

Будем говорить, что ученые А и В взаимны, если им понравились доклады друг друга. Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75). Рассмотрим всех, кому понравился доклад A , и всех, чьи доклады понравились А. Так как тех и других не менее, чем по 75, а всего ученых, кроме А, ровно 99, то найдется хотя бы 51 человек, взаимный с А. Возьмём группу из ровно 51 такого учёного (назовем её s). Для любого ученого из s найдется как минимум ученых из s, доклады которых ему понравились. Рассмотрим в s такого ученого B , доклад которого понравился наибольшему числу его коллег из s. Таких будет не менее 26. Тогда так как B понравились не менее, чем 26 докладов из s , среди учёных из s найдется C , который взаимен с B . Тогда и C попарно взаимны, что и требовалось доказать.

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2.

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2. Стало быть, всего таких маршрутов не более, чем . С другой стороны, пусть из данной вершины выходит и рёбер первого, второго, третьего и четвёртого цветов соответственно. Тогда число одноцветных маршрутов длины 2 , для которых эта вершина — средняя, равно . По неравенству между средним арифметическим и средним квадратическим имеем: . Таким образом, каждая вершина нашего графа является средней минимум для одноцветных маршрутов, причём минимум достигается только в случае, когда из вершины выходит ровно по 5 маршрутов каждого цвета. И только в этом случае сумма количеств одноцветных маршрутов длины 2 по всем вершинам равна 840, в остальных — больше. Но такой случай невозможен, потому что тогда, оставив в нашем графе только рёбра одного какого-то цвета, мы получили бы граф с нечётным числом нечётных вершин.

Допустим, утверждение задачи неверно для какого-либо графа на 2008 вершинах. Будем говорить, что вершина портит вершину , если вершину можно перекрасить так, чтобы вершина , которая не была плохой, стала плохой. Заметим, что если степень вершины не равна 2 , её можно испортить не более чем одним способом.

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

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

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

Каждую вершину можно перекрасить двумя способами. Поэтому количество способов, которыми можно испортить вершины нашего графа, равно . С другой стороны, столько же должно получиться, если просуммировать по всем вершинам количество способов, которыми они могут быть испорчены. Поскольку в этой сумме все слагаемые не больше 2 , все они должны равняться 2. Это возможно только если в нашем графе степень каждой вершины равна 2 . Стало быть, он распадается на непересекающиеся циклы, причём каждую вершину каждого цикла можно испортить двумя способами. Такое возможно только если каждая вершина и те вершины, что идут в цикле через одну от неё, покрашены в три разных цвета. Нетрудно показать, что длина цикла в этом случае должна делиться на 3 . Но 2008 на 3 не делится.

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Пусть — наш граф, — множество всех остовных деревьев графа , а М( ) — множество всех остовных подграфов графа , имеющих ровно один цикл. Рассмотрим произвольное дерево . В нем нечетное число ребер, следовательно, количество не вошедших в ребер графа также нечетно. Если к дереву добавить любое не вошедшее в него ребро графа , то получится граф из . Всего таким образом из дерева получается нечетное число графов из . Наоборот, рассмотрим любой граф и его единственный цикл . Граф может быть получен добавлением ребра к тем деревьям, которые получаются из удалением одного из ребер цикла . Так как граф двудольный, то в цикле — четное число ребер, следовательно, у графа — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве четное число остовных деревьев.

Построим новый граф, вершинами которого будут остовные деревья нашего графа.

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

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

Отметим мальчиков синими точками, девочек — красными, а тех, кто танцевал друг с другом, соединим линиями. По условию из всех синих точек выходит поровну линий, и потому общее число линий делится на 30 . Из красных точек может выходить линий. Заметим, что . Чтобы не нашлось двух девочек, танцевавших с одним и тем же количеством юношей, надо вычесть из этой суммы число от 0 до 30 так, чтобы разность разделилась на 30 . Но единственное подходящее для этого число 15 по условию вычесть нельзя.

Покажите, что в цвет правильно раскрасить все вершины можно всегда.

Ответ. В цвет.

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

Теперь покажем, что меньшего числа цветов может и не хватить. Расположим точек в виде прямоугольника из строк и столбцов. Примем это множество за . Снизу добавим нулевую строку из точек, примем ее за , слева нулевой столбец, примем его за . Ребрами в соединим любые две точки, не лежащие ни в одной строке, ни в одном столбце. В соединим рёбрами каждые две точки, в — тоже. Кроме того, соединим рёбрами каждую точку из со всеми точками из , не лежащими с ней в одном столбце, и каждую точку из со всеми точками из , не лежащими с ней в одной строке. Очевидны правильные раскраски в цветов (по столбцам) и в цветов (по строкам). Покажем, что полученный граф нельзя раскрасить меньше, чем в цвет. Допустим, есть правильная раскраска в цвета. Поскольку точки множества раскрашены в различных цветов, а точки множества — в различных цветов, то есть цветов (назовём их общими), в которые покрашены точки обоих этих множеств. Отметим строки и столбцы, в которых находятся такие точки; на их пересечении находится точек множества . Заметим, что в каждый из общих цветов может быть покрашено не больше одной из этих точек, а именно, точка, стоящая на пересечении соответствующих столбца и строки. Стало быть, среди этих точек есть точек, раскрашенных в другие цвета. Это не могут быть общие цвета, но не могут быть и другие цвета, использованные при раскраске точек множеств и , потому что со всеми точками таких цветов точки из отмеченных строк и столбцов связаны рёбрами. Всего при раскраске точек из и было использовано цветов. Из упомянутых выше точек можно выбрать точек, никакие две из которых не лежат в одной строке или одном столбце. Каждые две из этих точек связаны ребром, поэтому они раскрашены не менее, чем в цветов. Получается, что всего использовано не менее, чем цветов. Противоречие.

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

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

Зафиксируем десятерых, любые двое из которых знакомы. Назовём их синими, а остальных десятерых — зелёными.

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

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

Пусть — наши пары. Каждую девочку соединим с другой девочкой, знакомой с . В результате получится граф на вершинах , с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней вершин, тогда и рёбер в ней тоже (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.