Тема Иннополис (Innopolis Open)

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела иннополис (innopolis open)

Разделы подтемы Иннополис - задания по годам

Иннополис 2015 и ранее

Иннополис 2016

Иннополис 2017

Иннополис 2018

Иннополис 2019

Иннополис 2020

Иннополис 2021

Иннополис 2022

Иннополис 2023

Иннополис 2024

Иннополис 2025

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90003

Сколькими способами из множества ${1,2,3,...,2024}$ можно выбрать $n$ чисел так, чтобы сумма любых $m$ (произвольное натуральное число, меньшее $n$ ) из выбранных чисел не делилась на 3? Рассмотрите все возможные $n ≥ 2.$

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Нужно рассмотреть все натуральные n>=2... как будто это очень много чисел.. Значит, нужно как-нибудь сузить круг поиска. Подумайте, может ли n быть больше трех?

Подсказка 2

Правда ли, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём?

Подсказка 3

Это действительно так! Получается n<=3, то есть нам нужно рассмотреть всего два варианта! Для подсчёта используйте число сочетаний и рассматривайте остатки при делении на 3.

Показать ответ и решение

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

А значит, $n ≤3,$ при этом из условия нас интересуют $n≥ 2.$ В рассматриваемом множестве чисел по $675$ чисел, дающих остатки $1$ и $2$ при делении на $3.$

Тогда для $n= 3$ подходят любые три числа с одинаковыми остатками, их $3 2⋅C675.$ Для $n = 2$ любая пара чисел с ненулевыми остатками, то есть $2 2⋅C675$ пар чисел с одинаковыми остатками и $2 675$ с разными.

Итого $2 3 2 3 2 2 ⋅C 675+ 2⋅C675+ 675 =2 ⋅C 676+ 675 = 102971025$ чисел.

Ответ:

$2⋅C3 + 6752 = 102971025 676$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#90004

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

- если полицейский войдет в подъезд, в котором укрылся преступник, то гарантированно поймает его;

- если полицейский войдет в подъезд, где преступника нет, то с вероятностью $1 6$ тот убежит через выход из двора (и поймать его уже не удастся), с вероятностью $1 2$ преступник никуда не переместится, и с вероятностью $1 3$ спрячется в другом подъезде, где полицейского сейчас нет;

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

С какой вероятностью полицейский поймает преступника? Перемещения между подъездами можно считать мгновенными.

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

У нас получается бесконечный граф, но достаточно записать вероятности лишь нескольких первых ходов. Далее вероятности будут одинаковы: если полицейский не угадывает подъезд и преступник не сбегает, то вероятность не изменится. Мы можем составить уравнение.

Подсказка 3

Осталось только просуммировать вероятности, когда полицейский ловит преступника, и получить ответ.

Показать ответ и решение

С вероятностью $1 3$ полицейский поймает преступника в первом же подъезде, в который зайдёт, и с вероятностью $2 3$ преступника там не окажется, значит, с вероятностью $2 1 1 3 ⋅6 = 9$ преступник сбежит из двора (сразу после первого захода полицейского в подъезд), и с вероятностью $2 5 5 3 ⋅6 = 9$ преступник так или иначе окажется в одном из подъездов, где сейчас нет полицейского.

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

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

Заметим, что вероятность поймать преступника в точке $B$ равна вероятности поймать преступника в точке $C,$ обозначим эту вероятность за $P.$ Тогда, учитывая все возможные события в точке $B,$ получим $1 5- P = 2 + 12 ⋅P,$ отсюда $6 P =7.$ Учитывая события из точки $A,$ вероятность поймать преступника $1 5 17 3 + 9 ⋅P =21.$

Ответ:

$17 21$

Ошибка.
Попробуйте повторить позже

Задача 3#90009

Даны две окружности $Γ 1$ и $Γ 2$ , пересекающиеся в (несовпадающих) точках $A,B$ . К этим окружностям проведены общие внешние касательные, пересекающиеся в точке $X$ . Прямая $XA$ повторно пересекает $Γ 1$ в точке $T1$ , а прямая $XB$ повторно пересекает $Γ 2$ в точке $T2$ . Касательная к $Γ 1$ в точке $T1$ и касательная к $Γ 2$ в точке $T2$ пересекаются в точке $Y$ . Докажите, что точки $X,Y,T1,T2$ лежат на одной окружности.

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Если обозначить центр Г₁ за O₁, а центр Г₂ за O₂, то чертёж выглядит достаточно симметричным относительно O₁O₂. Но вот T₁ и Т₂ несимметричны. Давайте считать, что радиус Г₂ меньше Г₁. Тогда вторая точка пересечения XT₁ и окружности Г₂, пусть S, лежит на отрезке XT₁.

Подсказка 2

Через равенство углов ∠ XT₁Y и∠ XT₂Y!

Подсказка 3

∠ XT₂Y равен углу между XT₁ и касательной к окружности Г₂ в S(пусть β). Значит, теперь мы хотим показать, что β и ∠ XT₁Y равны. Как бы это сделать?

Подсказка 4

С помощью гомотетии в X! Но с каким коэффициентом?

Подсказка 5

С таким коэффициентом, чтобы при гомотетии S перешла в А.

Показать доказательство

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

$PIC$

Докажем, что прямая $XA$ составляет равные углы с касательной к $Γ 1$ в точке $T1$ и с касательной к $Γ 2$ в точке $S$ . Гомотетия с центром $X$ и коэффициентом $XA∕XS$ переводит $Γ 2$ в $Γ 1$ , при этом точки пересечения прямой $XA$ с окружностью $Γ 2$ переходят в точки пересечения $XA$ с $Γ 1$ в порядке их следования на луче $XA.$ Значит, точка $S$ перейдет в точку $A$ , а точка $A$ – в точку $T1.$

При гомотетии касательная к $Γ 2$ в точке $S$ переходит в касательную к $Γ 1$ в точке $A.$ Согласно теореме о б угле между касательной и хордой, касательные к $Γ 1$ в точках $A$ и $T1$ составляют равные углы с хордой $AT1,$ из чего следует, что прямая $XA$ составляет равные углы с касательной к $Γ 1$ в точке $T1$ и с касательной к $Γ 2$ в $S.$ Утверждение доказано. (Отметим, что если касательные из доказанного утверждения параллельны, то прямая $T1S$ содержит $Γ 1$ и $Γ 2,$ а значит точки $A$ и $B$ совпадают, что противоречит условию.)

Осталось доказать $∠YT1X = ∠YT2X.$ Для этого рассмотрим прямую $O1O2,$ являющуюся осью симметрии окружностей $Γ 1$ и $Γ 2,$ относительно неё симметричны прямые $XT1$ и $XT2,$ касательные к $Γ 2$ в $S$ и $T2.$ Значит, $∠YT2X$ равен углу между $XT1$ и касательной к $Γ 2$ в $S,$ этот угол равен $Y T1X.$

Ошибка.
Попробуйте повторить позже

Задача 4#90010

Про положительные числа $a,b,c$ известно, что $a +b+ c= 1$ , и каждое из них не превосходит $1 2$ . Докажите, что

√- √- √- ∘ -2--2---2 √- √ - √ - a+ b + c ≤ a + b+ c +2(b a+ c b+a c)

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Давайте подумаем, как можно применить то, что каждая переменная не превосходит 1/2. Например, можно получить выражение (1 - 2х), которое всегда больше 0. Как это сделать?

Подсказка 2

Мы можем всё, кроме корня из суммы квадратов, переместить влево. Тогда какое неравенство можно применить? Сумма скобок равна 1. На какое неравенство это может намекать?

Подсказка 3

Неравенство Йенсена! Его можно применить для корня, вогнутой функции. После недолгих преобразований под корнем не трудно прийти к искомому.

Показать доказательство

Перенесём влево $2(b√a-+c√b +a√c),$ чтобы вынести корни за скобки. Получаем, что нужно доказать:

√- √- √- ∘-2---2--2 a ⋅(1− 2b)+ b⋅(1− 2c)+ c⋅(1− 2a)≤ a + b +c

В силу того, что $a,b$ и $c$ меньше либо равны $1, 2$ числа $(1− 2a),(1− 2b),(1 − 2c)$ неотрицательны, а их сумма равна $1,$ ведь $a+ b+ c= 1.$ Функция $√x$ является вогнутой, тогда применив неравенство Йенсена для этой функции, переменных $a,b$ и $c,$ коэффициентов $(1− 2b),(1 − 2c)$ и $(1− 2a),$ получаем:

√- √- √- ∘--------------------------- a ⋅(1− 2b)+ b⋅(1− 2c)+ c⋅(1− 2a)≤ a ⋅(1− 2b)+ b⋅(1 − 2c)+c⋅(1− 2a)

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

a ⋅(1− 2b)+ b⋅(1 − 2c)+c⋅(1− 2a)=

= a⋅(a+ b+ c− 2b)+ b⋅(a+ b+ c− 2c)+c⋅(a+ b+c− 2a)=a2 +b2+ c2

Ошибка.
Попробуйте повторить позже

Задача 5#90011

Петя и Вася разыгрывают призовой фонд, содержащий перед началом игры натуральное число $M$ фунтиков. (Мы не знаем, что такое фунтики, но фунтики бесконечно делимы, например можно «отмерить» $√ - 1∕ 2$ фунтиков). Петя знает секретное (целое) число фунтиков $N$ (из диапазона $0≤ N ≤ M),$ которое ему нужно для поездки в Иннополис, а Вася должен угадать это число $N.$

Игра состоит из раундов «Васина догадка - Петин ответ», которые продолжаются, пока Вася не назовет число $N$ или пока не опустеет призовой фонд. В каждом раунде Вася называет целое число $k$ (из диапазона $0≤ k≤ M )$ и

- если $k <N,$ то Петя говорит об этом Васе, после чего игроки просто переходят к следующему раунду;

- если $k >N,$ то Петя говорит об этом Васе, забирает из фонда $M ∕3$ фунтиков, и если в фонде еще остались фунтики, то игроки переходят к следующему раунду;

- если $k =N,$ то Петя говорит об этом Васе, затем Вася получает из фонда $(x− n)$ фунтиков, где $x$ — количество фунтиков в фонде на данный момент, а $n$ — количество сыгранных раундов. Если $x ≤n,$ то Вася получит 0 фунтиков.

Какое наибольшее число фунтиков может гарантировать себе Вася?

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Давайте подумаем, какому условию должна удовлетворять стратегия Васи, иначе говоря, когда он ну точно не получит наибольшее вероятное количество фунтиков?

Подсказка 2

Если он 3 раза назовет число, большее N, то весь фонд уйдёт Пете. Можем сначала подобрать стратегию для Васи, а потом попробовать доказать, что она гарантирует наибольшее возможное количество фунтиков. Давайте рассматривать стратегии Васи с определёнными количествами "провалов" (когда Вася называет число k > N).

Подсказка 3

Давайте рассмотрим наименьшее число n, при котором n(n + 1)/2 ≥ M, и подумаем, какие шаги оптимально делать Васе до первого "провала".

Подсказка 4

Пусть Вася будет называть числа k₁ = n, k₂ = n + (n - 1), ... , kₘ₊₁ = n + (n - 1) + ... + (n - m), пока не угадает число N или не превзойдет его. Попробуйте придумать стратегию, при которой Вася будет совершать не более одного "провала".

Подсказка 5

Если Вася попадает в число N, то игра заканчивается. Иначе после провала он перейдет к угадыванию. Вася будет называть последовательные числа от kₘ₊₁ до N (в случае провала, N будет меньше kₘ₊₁). Сколько тогда фунтиков обеспечит себе Вася?

Подсказка 6

До kₘ₊₁ - (m + 1) раунд, до угадывания — не более (m +1) раунда, тогда Вася сыграет (m + 1) + (n - (m + 1)) раундов и получит (2M/3 - n) фунтиков. Надо теперь доказать, что эта стратегия оптимальна. Предположите для начала, что существует стратегия, при которой Вася может получить больше фунтиков.

Подсказка 7

Эта стратегия будет предписывать возрастающую последовательность чисел k₁ < k₂ < ... < kₜ, где t < n. Какое еще условие на k можно наложить через n? Попробуйте доказать через определение n, что такая стратегия не даст нам гарантированно больше фунтиков.

Показать ответ и решение

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

Стратегия Васи с одним “провалом”: пусть $y(y+1) n= {y| 2 ≥M }$ (т.е. наименьшее натуральное $n$ , при котором $n(n+1) 2 ≥ M$ ). Шаги до “провала”: Вася называет числа $k1 =n,k2 = n+ (n − 1),k3 =n +(n− 1)+(n− 2),...,$ пока Петя не скажет, что для очередного $km+1 =n +(n− 1)+...+(n− m)> N$ (первый "провал") или что угадано число $N.$ Сумма арифметической прогрессии $n(n+1) --2-- ≥M ≥N,$ а значит, такой момент обязательно наступит. Если это в момент первого “провала”, то в этот момент Петя получает из фонда $M -3$ фунтиков, в фонде остаётся $2M 3--$ фунтиков, а Вася приступает к выполнению шагов до "угадал".

Шаги до “угадал”: Вася называет (не более чем $(m + 1))$ последовательные числа от $(km+1)$ до $N$ (которое меньше $km+1$ ) до тех пор, пока Петя не скажет, что задуманное число угадано, а Вася, сыграв $n= (m + 1)+ (n− (m + 1))$ раундов, получает из фонда $(2M3-− n)$ фунтиков.

Докажем, что такая стратегия оптимальна. Пусть существует стратегия для Васи, позволяющая гарантированно получить больше фунтиков. Эта стратегия предписывает возрастающую последовательность чисел $k1 <k2 < ...<kt,$ где $t<n$ и $ki+1 < ki+(n− i)$ для любого $1≤ i< t.$ Но так как $n= min{y|y(y2+1) ≥M },$ то $kt < M,$ а значит, остались непроверенные числа от $(kt+1)$ до $M,$ и такая стратегия не может гарантированно улучшить результат.

Ответ:

$2M-− min{y|y(y+1)≥ M } 3 2$

Ошибка.
Попробуйте повторить позже

Задача 6#90012

В правильном $n$ -угольнике ( $n≥ 3$ ) Коля, аналитик платформы «AllCups», решил сопоставить отрезкам между вершинами (т.е. сторонам и диагоналям) их важности, т.е. натуральные числа, удовлетворяющие условиям:

1. для любого треугольника с вершинами в вершинах данного $n$ -угольника важности двух его сторон равны и превосходят важность третьей стороны;

2. важности всех отрезков должны образовывать отрезок натурального ряда, т.е. быть числами $1,2,3,...,k$ без пропусков, но с повторениями.

Найдите максимальное возможное $k$ .

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Задача вида «оценка + пример», поэтому хочется понять ответ. Например, для n = 3 и n =4 какие ответы?

Подсказка 2

Для n = 3 ответ совсем просто проверяется, для n = 4 чуть сложнее. Но из них можно предположить, что для произвольного n значение k не превосходит n-1. Причем для k = n-1 нетрудно строиться пример(один из вариантов — пронумеровать вершины от 1 до n, а стороны между i и (i < j) сделать равными какому-то выражению от j). Значит, можно попробовать доказать эту оценку, но как?

Подсказка 3

С помощью индукции! База уже есть. Пусть для всех n от 1 до p предположение верно, докажем для n = p + 1.

Подсказка 4

Например, что не бывает треугольника с двумя отрезками важности 1. Рассмотрите произвольный отрезок АВ с важность 1 и две произвольные точки С и D, отличные от А и В. Что можно сказать о важности АС и ВС, а о паре АD и BD?

Подсказка 5

Они совпадают. Что если попробовать «склеить» А и В? Тогда как раз получится р точек и можно будет использовать предположение индукции. Нужно лишь проверить, что «склеивание» будет происходить корректно.

Показать ответ и решение

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

База индукции: $n= 3.$ Если $k≥ 3,$ то стороны единственного треугольника обязаны быть $1,2,3,$ но это противоречит условию, о том, что в треугольнике есть две равные стороны.

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

Обозначим вершины отрезка важности $1$ как $A$ и $B,$ за $C$ и $D$ обозначим произвольные вершины $n−$ угольника (такие найдутся, так как $p +1≥ 4$ ). Покажем, что важности сторон треугольника $ACD$ не поменяются при замене $A$ на $B.$ Действительно, при такой замене отрезок $AC$ будет заменён на $BC,$ а отрезок $AD$ на $BD.$ Но поскольку оба треугольника $ABC$ и $ABD$ содержат отрезок $AB$ важности $1,$ то, согласно доказанному выше, важности пар сторон каждого треугольника равны. Значит, важности $AC$ и $BC,$ как и важности $AD$ и $BD$ совпадают.

Проделаем следующую процедуру: для отрезка $AB$ с важностью $1,$ эти две вершины склеим в одну вершину $X,$ и для каждой вершины $C$ важностью $XC$ будем считать равной важности $AC.$ Докажем, что многоугольник удовлетворяет первому условию и “ослабленному” второму, т.e. важности всех его сторон и диагоналей образуют отрезок $1,2,3,...,k$ или $2,3,...,k$ натурального ряда без пропусков. Действительно, для любого подходящего треугольника $XY Z$ нового многоугольника, если ни одна из вершин $X,Y,Z$ не была склеена с другой, то требование на важности сторон не изменилось. Если же какая-то вершина (без ограничения общности, вершина $X$ ) была склеена из вершин $A$ и $B,$ то, как было показано ранее, распределение важностей в треугольнике $XY Z$ будет таким же, как в треугольниках $AYZ$ и $BYZ,$ в каждом из которых первое условие было выполнено, а значит, оно не нарушилось и после склейки. Второе, "ослабленное"условие также будет выполнено, т.к. после склейки из набора важностей будет удалено $1.$

Проделав такую склейку по очереди с каждым отрезком важности $1$ получим $m −$ угольник $(m < n)$ , для которого выполнено первое и второе "ослабленное условия задачи". Для него понизим все важности на $1,$ и получим выполняющиеся условия для $m −$ угольника, значит, $k− 1≤ m − 1,$ откуда $k≤ m ≤n − 1.$ Индукция доказана.

Пример: Занумеруем все вершины $n−$ угольника числами от $1$ до $n,$ и зададим отрезкам, соединяющим вершины с номерами $i$ и $j$ $(i< j),$ важность $j− 1.$ Легко проверить, что оба условия на важности выполняются, и максимальная важность равна $n − 1.$

Ответ:

$n − 1$

Предыдущая подтема

Следующая подтема