Средняя сложность

Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

Ответ. . Решение. Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

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

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

База: очевидна.
Переход: от всех меньших к . Подвесим дерево за вершину и рассмотрим вершину самого нижнего уровня. Если у ее предка не менее трёх потомков, то выкинем и всех ее потомков.

В оставшемся дереве выберем хорошее множество и добавим всех потомков . Полученное множество будет хорошим для исходного дерева, и в нём не менее вершины.

Если у вершины ровно 2 потомка и , то рассмотрим её предка . Выкинем вершины и и, если понадобится, добавим рёбра для того, чтобы получилось дерево. В получившемся дереве выберем хорошее множество из не менее вершин, после чего добавим к нему вершины и .

Итак, мы можем считать, что у любой вершины с нижнего уровня предок имеет степень ровно 2. Пусть — вершина нижнего уровня, — её предок, — предок . У всех потомков (не обязательно прямых) степень 1 или 2 . Если у всего потомков (не обязательно прямых). Выкинем и всех её (не обязательно прямых) потомков. В оставшемся графе хорошее множество содержит не менее вершин. Добавим к ним всех потомков . Получим хорошее множество из не менее вершин в исходном дереве.

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

Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2.

Ответ. 2019.2018-1009 = 4073333.

Решение. Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2. Сумма написанных чисел будет как раз 2•(2019•2018/2). Оценка. Назовём вершину плохой, если из неё выходит больше одного ребра, помеченного единицей. Если в графе нет плохих вершин, то всё в порядке: ребер с единицами не больше 1009, и сумма написанных не ребрах чисел не меньше . Пусть плохая вершина есть. Возьмём ребро , на котором написана единица, и рассмотрим все треугольники вида . Если на одной из сторон или такого треугольника написана единица, то на другой должна быть тройка. Во всех таких случаях заменим эти единицу и тройку на две двойки. Сумма написанных на ребрах чисел при этом не изменится, сумма чисел на сторонах любого треугольника останется не меньше 5, а число плохих вершин уменьшится. Повторяя описанную процедуру, мы можем уничтожить все плохие вершины, а для графа без плохих вершин всё уже было доказано.

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

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

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

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

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

Таким образом, все наборы разбились на пары, то есть их четное число. Противоречие.

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

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми. Тогда у каждого человека знакомых минимум , а пяти попарно знакомых точно нет.
Докажем, что менее 2695 человек быть не могло. Предположим, что у нас людей. Тогда у каждого не более незнакомых. Будем набирать группу из попарно знакомых. Когда мы добавляем к ней любого человека, он запретит с учётом себя не более . Поскольку , то после того как наберём не более четверых, не запрещённые останутся, поэтому можно будет добавить человека в нашу группу. Получается, найдётся группа из 5 попарно знакомых.

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

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

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

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества , и от вершины к вершине идет синяя стрелка, если делится на , и красная, если делится на .

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

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

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

Ответ. 51 человек.

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

Пример. Пусть человек с номером знаком с людьми с номерами от до 99, других знакомств нет. Уходить они будут по порядку от 1 до 48 . На момент ухода -го человека: ему не знакомы только следующих за ним, остальным из этих 48 — хотя бы следующих и предыдущий, а последним 51 — хотя бы 50 , что тоже не меньше .

Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города и город соединен только с городом 100.

Ответ: 2500.

Решение. Оценка. Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города и город соединен только с городом 100. Предположим, что все города были посещены хотя бы три раза. Тогда есть хотя бы два города, которые соединены только с городом 100 . Но наибольший из таких городов может быть посещен только один раз (когда путешествие начинается в нем). Если все города посещены 1 раз, то в стране вообще нет дорог, что нас не устраивает. Значит, все города посещены ровно два раза. Удалим город 100 и город , соединенный только с ним. Мы удалили не более дорог. Для оставшейся части страны всё ещё верно утверждение, что при путешествиях с началом в каждом из городов, все города посещаются поровну раз, так как города и 100 посещались ровно 2 раза в путешествиях с началом и 100. Повторяя такие рассуждения, мы будем удалять пары городов, удаляя не более дорог. Значит, изначально в стране было не более 2500 дорог. Пример: при город соединим с городами с номерами хотя бы . Также соединим попарно города с номерами, большими 50. Тогда начиная в городе мы перемещаемся в город и останавливаемся. Значит, все города будут посещены дважды. И количество ребер равно .

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

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

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

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