Уральский Турнир Юных Математиков

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

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

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

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

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

Ответ. 14.

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

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

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

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых.

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых. Если таких пар наберется 25 , среди входящих в них 50 человек не найдется никого, кто был бы знаком с 49 остальными — противоречие. Значит, таких пар не больше 24 , и в них входит не больше 48 человек. Понятно, что среди 52 (или большего числа) остальных людей каждый знает каждого, что и требовалось доказать.

Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А.

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

Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой.

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

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

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

Ответ: Нет.

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

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

Ответ: .

Решение. Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых. Пусть оно равно . Тогда общее число знакомств среди 50 человек должно равняться . Значит, значение а будет одним и тем же для всех компаний из 51 человека. Возьмем любого человека Ч. Среди остальных 99 есть либо 50 знакомых с ним, либо 50 незнакомых с ним. Добавляя их к Ч, получим компанию, где в первом случае , а во втором . Но второй случай невозможен по условию, а в первом случае, очевидно, каждый знаком с каждым. Отсюда получаем ответ.

Заметим, что четность числа горящих лампочек в любой момент такая же, как в начальном состоянии. Устроим систему из 2004 выключателей следующим образом: одна лампочка А является выделенной, и каждый выключатель подключен к ней и еще какой-то из других лампочек (разные выключатели — к разным лампочкам).

Заметим, что четность числа горящих лампочек в любой момент такая же, как в начальном состоянии. Устроим систему из 2004 выключателей следующим образом: одна лампочка А является выделенной, и каждый выключатель подключен к ней и еще какой-то из других лампочек (разные выключатели — к разным лампочкам). Если в начальном состоянии горит четное число лампочек, то погасим их, последовательно выключая их и переключая лампочку А (в итоге все лампочки, включая А, будут погашены). Если же в начальном состоянии горит нечетное число лампочек, то включим все остальные (их четное число, поэтому в итоге лампочка А тоже будет включена). Докажем, что меньшего числа выключателей не хватит. Действительно, при меньшем количестве выключателей граф лампочек несвязен, поэтому есть или хотя бы одна четная компонента связности, или хотя бы три нечетных компоненты. В четной компоненте достаточно рассмотреть такое начальное состояние, в котором горит только одна лампочка (и с ним уже ничего нельзя сделать), а на двух нечетных компонентах достаточно зажечь 0 и 1 лампочек соответственно — тогда одну из компонент можно будет только погасить, а другую — только зажечь.

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

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