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

Докажите индукцией по 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 попарно знакомых.

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

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

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

Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно .

Введём граф, в котором вершины — города, рёбра — наличие авиасообщения. Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно . В таком графе рёбра могут быть либо внутри одного яруса, либо между ярусами с номерами, отличающимися на 1. Мы рассматриваем множества ребер, при удалении которых сохраняется ярус каждой вершины в нашем графе, будем называть их интересными. Если некоторое ребро соединяет две вершины одного яруса, то при включении или исключении интересность множества ребер не меняется. Таким образом, все интересные множества разбиваются на пары, что противоречит условию. Следовательно, в графе нет ребер, соединяющих вершины одного яруса. Тогда в любом цикле ярусы соседних вершин отличаются на 1 , тем самым они имеют разную четность. Значит, любой цикл в данном графе имеет четную длину, что и требовалось.

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

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