Иннополис - задания по годам → .10 Иннополис 2024

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

А значит, при этом из условия нас интересуют В рассматриваемом множестве чисел по чисел, дающих остатки и при делении на

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

Итого чисел.

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

Построим дерево, отображающее все возможные (на рёбрах написаны соответствующие условные вероятности):

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

Заметим, что вероятность поймать преступника в точке равна вероятности поймать преступника в точке обозначим эту вероятность за Тогда, учитывая все возможные события в точке получим отсюда Учитывая события из точки вероятность поймать преступника

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

Докажем, что прямая составляет равные углы с касательной к в точке и с касательной к в точке . Гомотетия с центром и коэффициентом переводит в , при этом точки пересечения прямой с окружностью переходят в точки пересечения с в порядке их следования на луче Значит, точка перейдет в точку , а точка – в точку

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

Осталось доказать Для этого рассмотрим прямую являющуюся осью симметрии окружностей и относительно неё симметричны прямые и касательные к в и Значит, равен углу между и касательной к в этот угол равен

Перенесём влево чтобы вынести корни за скобки. Получаем, что нужно доказать:

В силу того, что и меньше либо равны числа неотрицательны, а их сумма равна ведь Функция является вогнутой, тогда применив неравенство Йенсена для этой функции, переменных и коэффициентов и получаем:

Теперь заметим, что

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей (так как после третьего "провала"весь фонд уходит Пете). Сначала предложим стратегию, позволяющую Васе гарантированно получить указанное количество фунтиков, а потом докажем, что это максимальное количество, которое он может гарантировать.

Стратегия Васи с одним “провалом”: пусть (т.е. наименьшее натуральное , при котором ). Шаги до “провала”: Вася называет числа пока Петя не скажет, что для очередного (первый "провал") или что угадано число Сумма арифметической прогрессии а значит, такой момент обязательно наступит. Если это в момент первого "провала то в этот момент Петя получает из фонда фунтиков, в фонде остаётся фунтиков, а Вася приступает к выполнению шагов до "угадал".

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

Докажем, что такая стратегия оптимальна. Пусть существует стратегия для Васи, позволяющая гарантированно получить больше фунтиков. Эта стратегия предписывает возрастающую последовательность чисел где и для любого Но так как то а значит, остались непроверенные числа от до и такая стратегия не может гарантированно улучшить результат.

Перед нами задача вида “оценка пример”. Сперва докажем оценку. По индукции по будем доказывать, что наибольшее возможное значение не превосходит

База индукции: Если то стороны единственного треугольника обязаны быть но это противоречит условию, о том, что в треугольнике есть две равные стороны.

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

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

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

Проделав такую склейку по очереди с каждым отрезком важности получим угольник , для которого выполнено первое и второе "ослабленное условия задачи". Для него понизим все важности на и получим выполняющиеся условия для угольника, значит, откуда Индукция доказана.

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