Все задачи

Попробуйте для начала подумать над компанией из 150 человек.

Ответ: 151.
Решение: Допустим, удалось выбрать 151 человека, не знакомых друг с другом. У них вместе 453 знакомства с оставшимися 149 людьми, но у тех вместе всего 447 знакомств — противоречие. Таким образом, среди любых 151 человека найдутся двое знакомых. Покажем, что 150 человек, не знакомых друг с другом, могут найтись. Разобьём компанию на 50 шестёрок, каждую шестёрку — на две тройки, и пусть в каждой шестёрке каждый человек из одной тройки знаком с каждым человеком из другой; в набор из 150 человек возьмём по одной тройке из каждой шестёрки.

Для каждого разбиения чисел от 1 до занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Что можно сделать после этого?

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

Теперь построим аналогичное дерево для разбиений чисел от 1 до , где соседние числа находятся в разных подмножествах. Из его корня, помеченного единицей, ведет ребро в единственную вершину второго яруса, помеченную двойкой, а из неё — в две вершины третьего яруса, помеченные единицей и тройкой (двойка невозможна, поскольку тогда числа 2 и 3 попадут в одно подмножество). Далее дерево строится по индукции: если уже построены ярусов, то с каждой вершиной -го яруса связано вершин ( )-го яруса, помеченных числами от 1 до , исключая число, которым помечена вершина , где — наибольшее число на маршруте из в корень дерева.

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

Сколько боёв было сыграно в любой из школ?

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

Лемма: Ребра полного графа на вершинах можно раскрасить в цветов так, чтобы граф с ребрами любого цвета был двудольным.

Лемма: Ребра полного графа на вершинах можно раскрасить в цветов так, чтобы граф с ребрами любого цвета был двудольным.

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

Теперь перейдем к решению задачи. Легко покрасить вершины данного графа степени не более 1000 правильным образом в цветов (и даже в 1001 цвет). Теперь, рассмотрим раскраску в 10 цветов ребер полного графа на 1024 вершинах (вершины которого занумерованы цветами вершин графа ), в которой граф каждого цвета двудолен. Покрасим все ребра графа между вершинами цветов и также, как и ребро между вершинами и в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.

Зафиксируйте 80 вершин со степенями соответственно.

Рассмотрим двудольный (мульти)граф, где вершины — блондинки и брюнетки, а рёбра — выборы мальчиков. В нем 2016 рёбер. Надо доказать, что есть два ребра с общими концами.

Зафиксируем 80 вершин со степенями соответственно; назовём их выбранными. Пусть имеется рёбер, оба конца которых выбраны; также назовём их выбранными. Тогда рёбер, один конец которых выбран, будет . С другой стороны, их не больше, чем 2016- , откуда .

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

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

Ответ: 32.

Решение: Оценка. По первому условию для каждых двух клубов и найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах. Отсюда следует, что четверки, соответствующие разным парам клубов, не пересекаются. Отсюда , то есть . Пример. Выделим среди жителей города непересекающихся четверок. Каждой из них поставим в соответствие пару клубов, в которых жители, входящие в неё, они не состоят, так, чтобы каждой паре клубов соответствовала какая-то четверка. Остальные (не входящие в четверки) жители состоят во всех клубах.

Разделите вершины на две равные группы и .

Рассмотрим граф знакомств. Разделим вершины на две равные группы и . Пусть — сумма степеней вершин, входящих в , а — количество знакомств между учениками из и . Тогда количество знакомств внутри равно . 1) Пусть у всех одинаковое число друзей. Тогда при разбиении на равные группы и , следовательно, . 2) Пусть не у всех одинаковое число друзей. Составим из вершин с наименьшими степенями. Тогда , и, следовательно, .

Пусть из Иксии в Игрекию ведёт дорог. Сколько ещё дорог в республиках?

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

Для каждой комиссии создайте антикомиссию из всех не входящих в эту комиссию депутатов.

Ответ: 9.

Решение: Для каждой комиссии создадим антикомиссию из всех не входящих в эту комиссию депутатов. В каждой антикомиссии не меньше 11 депутатов, и разные антикомиссии не пересекаются (иначе в две соответствующие комиссии входили бы не все депутаты). Поэтому антикомиссий, а, стало быть, и комиссий не больше 9. Пример на 9: нумеруем депутатов числами от 1 до 100, и в -ую комиссию включаем всех, чей номер при делении на 9 даёт остаток, не равный .

Пусть первую республику со второй соединяют дорог. Тогда сколько дорог внутри республик?

Пусть первую республику со второй соединяют дорог. Тогда сумма количеств дорог, выходящих из городов первой республики, равна , и всего внутренних дорог в первой республике окажется ( ) , так как каждая из них учтена дважды. Аналогично показываем, что во второй республике также ( ) 2 внутренних дорог.