Все задачи

Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл.

Ответ. Вася.

Решение. Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл. Значит, концы цепи длины 2 соединять с другими точками нельзя. Стратегия Васи: после каждого хода Пети соединять ту же красную точку с какой-то синей, которая ещё не соединена ни с какой другой. Тогда после каждой пары ходов Пети и Васи число не соединённых с другими синих точек будет уменьшаться на 2 , и после 50 -го хода Васи каждая синяя точка будет концом цепи длины 2. Своим 51-м ходом Петя создаст цепь длины 3 и проиграет.

Докажите индукцией по n

Ответ: последовательностей. Решение. Докажем это индукцией по . База очевидна.

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

— выбрать периферийную площадь, которую мы будем считать красной (это можно сделать способами),

— взять реестр остальной части города с улицами (по индукционному предположению имеется вариантов такого реестра),

— в любое место этого реестра вставить запись о красной площади ( вариантов)

— и добавить в конец запись о красной улице.

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

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

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

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

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

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

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

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

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

Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Ответ: 40 школьников.

Решение. Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Оценка. Предположим, что у какого-то школьника есть хотя бы 21 знакомый . По условию, все его знакомые незнакомы. Но тогда у школьника есть 20 незнакомых и они незнакомы друг с другом. Противоречие. Следовательно, у каждого школьника не более 20 знакомых и, аналогично, не более 20 незнакомых. Тогда школьников всего не более 41. Осталось доказать, что невозможен случай, когда школьников ровно 41 . Пусть так. Тогда у школьника ровно 20 знакомых и ровно 20 незнакомых . Причем все попарно незнакомы, а все попарно знакомы. У также должно быть ровно 20 знакомых, которые незнакомы между собой. Он уже знает и не знает никого из . Следовательно, он знаком с хотя бы 19 школьниками из . Но попарно знакомы. Противоречие.

Пример. Выберем 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 попарно знакомых.

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

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

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

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

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

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить городов в красный, а других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд зелёных и красных символов (способов сделать это ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить городов в красный, а других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд зелёных и красных символов (способов сделать это ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

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

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