Турнир городов - задания по годам → .01 Турнир городов 2015 и ранее

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

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

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

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

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

Значит, какую бы цифру мы не прибавили, мы прибавим что-то нечетное, а сумма двух нечетных(нашего числа и выбранной цифры) четна. Итак, мы получим четное число в последовательности.

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

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

Сначала оценим наименьшее число ходов. Чтобы попасть на противоположную сторону доски, фишке надо сделать семь вертикальных ходов. Но хотя бы одна из двух фишек, стоящих на одной вертикали, должна сделать горизонтальный ход (иначе им не разминуться). Поэтому вместе эти фишки сделают не менее 15 ходов. А таких пар на доске восемь. Значит, менее чем за 120 ходов добиться требуемой расстановки нельзя.

Придумаем алгоритм. Разобьём фишки на четвёрки, стоящих на двух соседних вертикалях. Каждую четвёрку передвинем за 30 ходов так, как показано на рисунке:

"Потери"на горизонтальные ходы происходят только на втором и четвёртом этапах.

(a) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое — стрелкой, соединяющей соответствующие точки (то есть построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния Получаем последовательность состояний Поскольку число состояний конечно, в некоторый момент в последовательности возникнет повторение. Пусть, например, где Поскольку в точку входит ровно одна стрелка, из равенства следует Тем самым, через ходов мы вернулись в состояние

(b) В отличие от первого пункта теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам.

Заметим, что если ход ведет из состояния в состояние то, согласно первому пункту, мы можем (за несколько ходов) вернуться из в Если мы можем попасть из состояния в состояние за несколько ходов, то мы можем вернуться из в “откатывая” ходы по одному. Теперь понятно, что если мы научимся попадать из любого состояния в некоторое фиксированное состояние то сможем “путешествовать” между любыми состояниями, “проезжая” через

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

Впишем в каждую белую клетку число 1, а в каждую чёрную — Пусть — сумма чисел, стоящих в -й строке, — сумма чисел, стоящих в -м столбце, — число, стоящее на пересечении этих строки и столбца.

Условие эквивалентно выполнению неравенств при всех и Действительно, разность между количествами белых и чёрных клеток, которые бьёт ладья с клетки равна Если, например, то

Наконец,

Таким образом, все суммы и равны нулю.

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

Рассмотрим проекции и векторов и на хорду — середина хорды , поэтому

и — середины хорд и , поэтому

Таким образом, .

Аналогично равны проекции векторов и на хорду . Но вектор полностью определяется своими проекииями на две непараллельные прямые. Поэтому

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

Поскольку касается прямой то Из параллельности и получаем Тогда а значит, касается

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Давайте думать о клетках, как о вершинах графа. Ребра будут общими сторонами, а если есть перегородка, то ребро убираем. Хорошим лабиринтам соответствует связный граф. Заметим, что в связном графе на вершинах должно быть хотя бы ребра. А значит, хороший лабиринт содержит не более перегородок. Давайте рассмотрим какой-нибудь лабиринт и определим для него инвертированный лабиринт, то есть в нашем графе мы убираем ребра и добавляем ребра, которых не было. Тогда мы получаем соответствие лабиринтов с перегородками лабиринтам с перегородками. То есть каждому хорошему лабиринту мы точно сопоставили плохой. А у нас точно еще есть плохие лабиринты, поэтому плохих лабиринтов точно больше.

Пусть первоначальная последовательность была Введём новую последовательность посчитаем разность для

Тогда Поскольку то что и требовалось.

Заметим, что середина отрезка является центром окружности Аполлония точек и с коэффициентом Поэтому можно предположить, что — центр окружности Аполлония и доказать, что — касательная к описанной окружности. Это равносильно изначальной задаче, потому что касательная пересекает в одной точке.

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

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

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

Оценка: Рассмотрим произвольное разбиение пирога объёма и построим по нему граф. Пусть вершинами графа будут гости (всего вершин). По каждому куску строим ребро, соединяющее двух гостей, которым достаётся этот кусок при первой и второй раздаче. Рассмотрим одну из компонент связности. Сумма «объёмов» её рёбер (то есть объёмов кусков, соответствующих рёбрам) должна быть кратна как так и (это следует из того, что если человек есть в этой компоненте, то в ней есть рёбра, соответствующие всем кускам, которые ему полагаются, поскольку на каждый кусок претендует как человек из первой группы, так и человек из второй), значит, она равна Следовательно, граф связен, поэтому число его рёбер не меньше

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

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

(c) Предположим, что мы хотим преобразовать в где и — два произвольных разбиения. Пусть — вершшна, из которой выходит хотя бы одна диагональ — перестройка, определенная в (b). Покажем, что можно преобразовать в добавляя при каждой перестройке по одной диагонали, выходящей из Пусть диагональ ещё не проведена. Тогда её начало принадлежит одному из треугольников разбиения, причем — диагональ. Поэтому к ней с другой стороны прилегает некий треугольник разбиения ( может совпадать с Сделав flip четырёхугольника мы добавим диагональ Итак, для указанного преобразования нужно не более перестроек. Для преобразования в необходимо столько же flip-oв, сколько для обратного преобразования в то есть не более поскольку одна диагональ уже стоит на своём месте.

Первое решение.

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

Второе решение.

Из равнобедренности . Для с радиусом описанной окружности применим теорему синусов и получим . Заметим, что лежит на серединном перпендикуляре к и удалён от и на расстояние . Но тогда в силу единственности центра описанной окружности он и будет центром (заметим, что он лежит по противоположную от сторону от вершины , ведь тупой). Отсюда .

Будем доказывать, что, если в классе человек и выбрана различная тройка детей, то найдутся две тройки, пересекающиеся ровно по ребёнку, либо такой конфигурации не существует (для ). Доказывать будем индукцией по

База для верна.

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