8 класс

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

Назовём десятерых, о которых идёт речь в задаче, знатоками, а остальных членов кружка — дружками. Будем говорить, что знаток портит пару дружков, если он не знает никого из этой пары. По условию каждый знаток знает более 4.101/5, то есть не меньше 81 дружка. Значит, он незнаком самое большее с 20 дружками и может испортить максимум пар дружков. Стало быть, вместе все 10 знатоков могут испортить максимум 1900 пар дружков, а всего пар дружков — . Поэтому найдется неиспорченная пара дружков (и даже не меньше 3150 таких пар), что и требовалось доказать.

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

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

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

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

Рассмотрим две вершины и , путь между которыми содержит наибольшее количество рёбер.

Ответ. При . Решение. Введём граф городов и авиарейсов. Для начала приведём пример графа, в котором меньше чем 1344 стратегически значимыми вершинами не обойтись. Пусть в графе имеются вершины , а также и ; для каждого проведём рёбра между вершиной и и , и . Легко видеть, что этот граф связен. Поскольку вершина связана только с вершиной , то вершина должна быть объявлена стратегически значимой. Кроме того, применяя условие задачи для вершины получаем, что либо вершина , либо вершина должна быть объявлена стратегически значимой. Итак, из вершин хотя бы две вершины должны быть стратегически значимыми. Рассуждая аналогично для каждой тройки , получаем требуемое.

Докажем теперь, что 1344 стратегически значимыми вершинами можно обойтись. Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

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

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

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

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

Будем продолжать эту деятельность, пока от графа не останется огрызок, содержащий не более двух вершин. Если вершин не осталось вообще, то мы объявили стратегически значимыми не более вершин, и процесс завершился. Если осталась одна вершина, то на предыдущем шаге нашего алгоритма она называлась и была соединена с вершиной или , которую объявили стратегически значимой, значит, для нее условие выполнено, и стратегически значимыми было объявлено не более вершин. Если же осталось две вершины, то, во-первых, они смежны, так как граф связности не теряет; во-вторых, одна из этих двух вершин была соединена с вершиной или , объявленной стратегически значимой на предыдущем шаге. Поэтому достаточно объявить стратегически значимой лишь одну из этих двух вершин, чтобы условие выполнялось. Значит, и в этом случае стратегически значимыми будет объявлено не более вершин.

Сопоставим каждой команде свою пятерку судей.

Ответ. Можно.

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

Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами.

Ответ: .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.

Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь).

Ответ: не обманывает.

Решение. Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь). Новые вершины будем считать «тощими». Возьмём произвольную нечётную раскраску полученного графа. Для любых двух толстых вершин и рассмотрим тощую вершину , соединенную с ними. Так как у вершины в этом графе всего две соседние вершины (это как раз и ), эти вершины должны быть окрашены в разный цвет. Итак, любые две толстые вершины должны быть разного цвета, следовательно, в раскраске используется не меньше 1022 цветов.

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

Будем доказывать индукцией по , что дерево на вершинах имеет не более (толстых) паросочетаний с независимыми рёбрами. Как выглядит дерево, если и толстых паросочетаний ровно ? А при ?

Решение. Будем доказывать индукцией по , что дерево на вершинах имеет не более (толстых) паросочетаний с независимыми рёбрами. Причём если и толстых паросочетаний ровно , то дерево является путем. А при граф является или путем, или «графом-ёжиком».

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

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

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

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

Пусть Петя — школьник, который ходит в кружков. Посмотрим на два какие-то кружка, в которые он не ходит. Они состоят из разных наборов участников, значит, найдется школьник Вася, который ходит в один из этих кружков, а в другой не ходит.

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

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

Ответ. 14.

Решение. Оценка. Всего троек команд можно составить . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда. С другой стороны, каждая команда является плохой самое меньшее в трех тройках. В самом деле, если она играла в один и тот же вид спорта хотя бы с тремя командами, то она образует не разносторонние тройки с каждыми двумя из них. Иначе она играла в каждый вид спорта с двумя командами, и три не разносторонние тройки тоже налицо. Таким образом, не разносторонних троек хотя бы , а разносторонних — не более . Пример. Расставим команды по кругу, и пусть в футбол, баскетбол и волейбол играют между собой те, между которыми по часовой стрелке нет других команд, одна другая команда и две другие команды соответственно. Нетрудно проверить, что тогда получится ровно 14 разносторонних троек.

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

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