Подсчёты в графах

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

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

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

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

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

Ответ: 32.

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

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

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

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

Ответ: 9.

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

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

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

Пусть девочек . Тогда каждый из друзей Васи не дружит с девочками.

Ответ: 11.

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

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

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

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

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

Ответ: 5.

Решение. Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих. Так ему после первого боя удастся сделать так, чтобы невезучих было не более 15, после второго — не более 7 , после третьего — не более 3 , после четвертого — не более одного. С другой стороны, если дети каждый раз будут делиться так, чтобы количества невезучих в двух командах отличались не более, чем на 1 , Дмитрию Андреевичу не удастся сделать всех везучими за 4 боя.

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

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

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

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