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

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

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

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

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

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

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

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

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

Иннополис 2016

Иннополис 2017

Иннополис 2018

Иннополис 2019

Иннополис 2020

Иннополис 2021

Иннополис 2022

Иннополис 2023

Иннополис 2024

Иннополис 2025

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

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

Задача 1#65459

Найдите все функции $f(x)$ , которые при любых вещественных $x,y$ удовлетворяют равенству

(2 ) ( 2 ) 4 f x + y = f x − y + 2x f(y)

Источники: Иннополис-2022, 8-9 (см. dovuz.innopolis.university)

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

Подсказка 1

В аргументах функции f фигурируют х^2 и у. Это говорит о том, что их можно воспринимать как 2 переменные и пытаться делать подстановки х^2 и у по отдельности.

Подсказка 2

Чтобы избавиться от одной из двух переменных, можно применить подстановку х:=0 или у:=0. Эти подстановки дадут нам информацию про значение в нуле и чётность функции.

Подсказка 3

Ещё одна “классическая” подстановка для избавления от одной из двух переменных — x^2=у и x^2=-y (в нашем случае именно эти величины мы воспинимаем как переменные).

Подсказка 4

Данных подстановок должно быть достаточно! Осталось лишь собрать вместе всю полученную информацию про функцию f и получить ответ!

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

Во-первых, подставим $y =0$ и получим равенство $2x4f(0)= 0$ , $x$ может принимать любые значения, поэтому $f(0)=0$ . Во-вторых, подставим $x= 0$ и получим $f(y)=f(−y)$ , то есть функция является чётной. Теперь подставим $2 y = x$ и $2 y =− x$ . Получим равенства $2 4 2 f(2x)= 2x f(x )$ и $2 4 2 0= f(2x )+2x f(x )$ . Подставим результат первого равенства во второе: $4 2 0= 4x f(x )$ . Получаем, что $2 f(x )= 0$ . Следовательно, во всех положительных точках функция равна $0$ , поскольку $2 x$ пробегает все положительные значения. В силу чётности получаем, что $f(x)= 0$ при всех $x$ .

Ответ:

$f(x)= 0$

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

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

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

Задача 2#74911

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

Известно, что среди всех марсиан, у которых не меньше двух глаз, каждую секунду в среднем $80%$ отдыхают, а среди тех, у которых не больше двух глаз, каждую секунду отдыхают в среднем $2 3$ марсиан. Найдите долю двуглазых марсиан среди всех марсиан.

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

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

Подсказка 1

Нам даны условия на количество отдыхающих в каждую секунду. А можем ли мы посчитать вероятность того, что марсианин отдыхает в данную секунду? Если получится, то можно составить уравнения на данные из условия!

Подсказка 2

Каждый марсианин каждую секунду отдыхает с вероятностью 1-(0.5)^k, где k - количество его глаз. Составим уравнения на данные условия и попробуем сделать какие-нибудь преобразования и выводы!

Подсказка 3

Составим систему и при её решении сделаем замену отношения количеств марсиан :) Таким образом мы сможем посчитать, чему отношение одноглазых к двуглазым и трехглазых к двуглазым! Теперь узнать долю двуглазых не составит труда)

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

Пусть $n k$ — количество марсиан, у которых $k$ глаз $(k= 1,2,3).$ Такой марсианин каждую секунду отдыхает с вероятностью $1− 0.5k,$ поскольку события "марсианин отдыхает"и "все глаза марсианина открыты"образуют полную группу событий, поэтому сумма их вероятностей равна 1. Сначала рассмотрим случай, когда $n2 ⁄= 0.$

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

2 (1− 0.5)n1+(1− 0.52)n2 n + 0.5n 3 = ------n1+-n2-------= 1− 0.5⋅-1n1+-n22

Аналогичная вероятность для марсиан, у которых не меньше двух глаз, равна

( ) ( ) 0.8= -1− 0.52-n2+-1−-0.53n3-= 1− 0.25 ⋅ n2+0.5n3 n2+ n3 n2+n3

Разделим числители и знаменатели полученных дробей на $n ⁄= 0 2$ и обозначим $x= n1,y = n3+-n2 n2 n2$ $($ тогда искомое отношение $n--+nn2+-n- 1 2 3$ преобразуется к виду $x-+1y+-1).$ Получим систему уравнений

( ( |{ 0.5x +0.25 = 1(x +1) |{ x= 0.5 1 6 |( 3 =⇒ |( 2 =⇒ x+-y+-1 = 13 0.125y+ 0.25= 0.2(y+1) y = 3

Теперь рассмотрим случай, когда $n2 = 0.$ Тогда доля отдыхающих марсиан среди тех, у кого не больше двух глаз, должна быть равна доле отдыхающих одноглазых марсиан, т.е. $0.5.$ Однако, согласно условию, эта доля равна $2 3 ⁄= 0.5$ — получили противоречие, значит, $n2 ⁄= 0.$

Ответ:

$-6 13$

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

Задача 3#74912

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

Например, если Иван играл черными фигурами в помещении №1, то он уже не сможет сыграть белыми фигурами в этом помещении. Аналогично, если участник играл белыми фигурами в помещении №5, то в этом же помещении он уже не сможет играть черными фигурами. При этом он может снова играть белыми фигурами в помещении №5.

Известно, что каждый участник турнира должен сыграть с любым другим участником ровно одну партию. Организаторы хотят составить такое расписание, чтобы задействовать минимально возможное число помещений. Докажите, что это число равно $⌈log2n⌉.$

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

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

Подсказка 1

Давайте попробуем доказать, что нам понадобиться не менее, чем [log_2(n)] (под [x] подразумевается целочисленное x округление вверх) комнат и что именно [log_2(n)] достаточно. Для док-ва первого утверждения давайте для удобства заведём функцию f(n) - искомое кол-во помещений от кол-ва участников. И построим док-во по сильной индукции.

Подсказка 2

Рассмотрите какое-то помещение и разбейте множество игроков на тех, которые играли и не играли белыми фигурами. Что мы можем сказать про кол-во участников в одном из получившихся множеств?

Подсказка 3

В каком-то из множеств не более n/2 элементов, пусть в том, которые играли белыми фигурами, тогда не играли ими не менее n/2 элементов и им хватило на 1 помещение меньше, чем n игрокам, какую оценку мы тогда можем получить на f?

Подсказка 4

f(n) - 1 >= f([n/2]), применяя ПИ индукции получим f(n) - 1 >= [log_2([n/2])] <=> f(n) >= [log_2(n)], теперь осталось придумать пример рассадки.

Подсказка 5

Давайте попробуем переформулировать задачу в терминах ориентированного графа, пусть вершины - шахматисты, ориентируем ребро ij, если i > j (i играет белыми, а j - чёрными). Поставим каждому ребру число k - наибольшее такое число, что в двоичной записи числа i на k-м месте стоит 1, а у j - 0. Осталось только доказать, почему такой пример - верный.

Подсказка 6

Посмотрите, сколько всего может быть цифр в числах i, j и почему рёбрам ij, jl соответствуют разные номера, и задача решена!

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

Пусть $f(n)$ — искомое число помещении в зависимости от количества $n$ участников турнира. Сначала докажем индукцией по $⌈log n⌉ 2$ , что $f(n)≥ ⌈log2n⌉.$ База $($ для $n = 3$ и $n = 4)$ очевидна.

Зафиксируем помещение (например, №1) и обозначим через $U1$ множество шахматистов (вершин графа, каждое ребро которого соответствует определенной партии), которые играли в этом помещении белыми фигурами. Аналогично, обозначим за $U2$ множество шахматистов, которые не играли в этом помещении белыми фигурами. Множества $U1$ и $U2$ не пересекаются — значит, хотя бы одно из них $($ без ограничения общности будем считать, что это $U1)$ содержит не более $n∕2$ элементов, остальные шахматисты (их не менее $n∕2$ ) не играли белыми фигурами в помещении №1 — значит, им для этого хватило $f(n)− 1$ помещений:

f(n)− 1≥ f(⌈n∕2⌉)≥ ⌈log2(⌈n∕2⌉)⌉

f(n)≥⌈log2n⌉

Покажем, как сделать "правильное"(т.е. соответствующее условию задачи) расписание с $f(n)=$ $⌈log n⌉. 2$ Для этого занумеруем вершины графа (т.е. шахматистов) числами от $0$ до $n − 1$ и ориентируем ребра графа (т.е. партии) $ij,$ если $i> j$ (шахматист $i$ играет белыми, а $j$ — черными), а помещения занумеруем числами от $0$ до $⌈log2n⌉.$ Ребру $ij$ поставим в соответствие номер $k,$ который определяется как наибольшее $k,$ такое, что в двоичной записи числа $i$ на $k$ -м месте стоит 1, а у числа $j$ — $0.$ Такое $k$ существует, поскольку $i⁄= j.$ Кроме того, в двоичных разложениях $i,j$ не более $⌈log2n⌉$ цифр, откуда $k ≤⌈log2n⌉.$

Осталось проверить, что ребрам $ij$ и $jl$ соответствуют разные номера. Действительно, если бы им соответствовал общий номер $k,$ то у числа $j$ в $k$ -м разряде двоичной записи стояла бы и цифра $0$ $($ из-за ребра $ij),$ и цифра $1$ $($ из-за ребра $jl),$ что невозможно.

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

Задача 4#74913

Два игрока играют в игру: они по очереди вытаскивают камни из кучки, в которой изначально было $n$ камней. В свой первый ход первый игрок берет из кучи один или несколько камней, но не может забрать все камни. Каждым следующим ходом очередной игрок должен забрать из кучи количество камней, являющееся делителем числа камней, забранного противником на предыдущем ходу, и не превосходящее числа камней в куче. Выигрывает тот, кто заберет последний камень. Для каждого $n> 1$ определите, у кого из соперников есть выигрышная стратегия.

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

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

Подсказка 1

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

Подсказка 2

Да, может, если количество камней в куче изначально нечётно! Для четных n похожую идею применить уже не получится. Тогда давайте посмотрим, что происходит при малых n, возможно увидим закономерность?

Подсказка 3

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

Подсказка 4

Да, мы поняли, что для n = 2 и n = 4, предположение выполняется(есть база), тогда давайте заметим, что первый игрок может взять количество камней в два раза больше, чем взял бы в игре с n/2 камнями, а этот случай уже попадает в индукционное предположение! Остаётся показать, что происходит, когда n является степенью двойки и соответственно есть выигрышная стратегия у второго игрока.

Подсказка 5

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

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

Заметим, что если в куче нечетное число камней, то первый игрок гарантирует себе победу, взяв на первом ходу 1 камень: тогда каждым следующим ходом игроки будут забирать по одному камню, и последний камень заберет первый игрок. Когда $n$ чётно, тот, кто первым сделает нечетный шаг, проиграет: такой шаг был сделан из четного числа — значит, он не будет последним, а противник заберет один камень, что и обеспечит ему победу.

Если $n= 2,$ то второй игрок, очевидно, побеждает. Если $n =3,$ то побеждает первый игрок, забирая первым ходом 1 камень. Если $n =4,$ то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.

Докажем по индукции, что для всех четных $n$ от $k− 1 2 +1$ до $k 2 − 1$ (для натурального $k ≥2$ ) побеждает первый игрок, а для $k n =2$ — второй. База индукции $(k = 2)$ разобрана выше.

Пусть $2k−1+ 1≤ n≤ 2k− 1$ для натурального $k≥ 3.$ Тогда первый игрок сводит игру к таковой с $n∕2$ камнями (т.е. берет вдвое больше камней, чем взял бы в игре с $n∕2$ камнями), где у него есть победная стратегия согласно предположению индукции, поскольку $2k−2+ 1≤ n∕2 ≤2k−1− 1.$ Единственный способ помешать ему — взять нечетное число камней, но, как показано выше, тот, кто первым возьмет нечетное число камней, проигрывает.

Пусть теперь $n= 2k$ для $k ≥3.$ Тогда уже второй игрок применяет стратегию "половинчатой"игры, т.е. берет в 2 раза больше камней, чем взял бы в игре с $n∕2$ камнями. Согласно предположению индукции, это обеспечит ему победу.

Ответ:

При $n= 2k, k∈ ℕ,$ второй игрок может гарантировать себе победу. При прочих $n> 1$ выигрышная стратегия есть у первого игрока.

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

Задача 5#74914

Назовём бесконечную числовую последовательность ${a } n$ стабилизирующейся, если при некотором $k 0$ для всех $k ≥k 0$ выполнено $ak = ak+1.$ Тогда $k0$ назовем временем стабилизации, $ak$ $($ при $k≥ k0)$ — стабильным значением.

Пусть $a,b$ — натуральные числа. Дана последовательность ${xn},$ в которой $x1 = x2 = x3 = a$ и для любого натурального $n$ выполнены равенства

x3n+1 = b⋅x3n−2,x3n+2 = x3n−1∘b

$($ здесь $∘b$ — это операция взятия целой части при делении на $b)$ и

x3n+3 =x3n+ x3n−2 ⋅(x3n− 1(modb))

$($ здесь $(modb)$ — операция взятия остатка от деления на $b).$

Какие из последовательностей ${x3n+1},{x3n+2},{x3n}(n∈ ℕ)$ стабилизируются, и чему равны их стабильные значения? Чему равно время стабилизации последовательности ${x3n}?$

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

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

Подсказка 1

Давайте посмотрим, что нам известно из условия? Получается, основная последовательность {Xn} разделяется на три подпоследовательности. Причём первые две, похоже, зависят только от тех элементов основной последовательности, что входят в эту подпоследовательность. Может, для начала рассмотрим их повнимательнее?

Подсказка 2

Верно, мы можем выразить элементы этой последовательности через a, b и n. Третья же подпоследовательность зависит от элементов из других подпоследовательностей, так что здесь так просто не получится расписать. Тогда стоит попробовать выразить x{3n+3} с помощью x{3n+1} и x{3n+2}. Например, записать какое-нибудь равенство с этими тремя переменными.

Подсказка 3

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

Подсказка 4

Остаётся только проанализировать, при каких значениях b каждая из подпоследовательностей стабилизируется и на каком стабильном значении

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

Сначала рассмотрим последовательность ${x }. 3n+1$ По ее определению имеем $x = a⋅bn 3n+1$ для всех целых $n ≥0$ — значит, при $b= 1$ ее стабильное значение равно $a,$ а при $b >1$ она не стабилизируется.

Теперь рассмотрим ${x3n+2}.$ По определению, если $b= 1,$ то $x3n+2 =a$ для всех целых $n≥ 0,$ а если $b> 1,$ то $-a x3n+2 ≤ bn$ и, поскольку последовательность — целочисленная, имеем $x3n+2 =0$ для всех $n,$ начиная с $⌈logba⌉$ (целая часть от логарифма, взятая с избытком).

Докажем по индукции, что

x3n+1⋅x3n+2+ x3n+3 =a2+ a

для всех целых $n ≥ 0.$

База индукции $(n= 0):$

2 x1⋅x2+ x3 =a + a

по определению.

Индукционная гипотеза: пусть для некоторого $m ≥0$ выполнено

2 x3m+1 ⋅x3m+2+ x3m+3 = a + a

Тогда

x ⋅x +x = (b⋅x3m+1)⋅(x3m+2 ∘b)+ 3(m+1)+1 3(m+1)+2 3(m+1)+3

+(x3m+3+ x3m+1 (x3m+2(modb)))= ((b⋅x3m+1)⋅(x3m+2 ∘b)+

2 x3m+1 (x3m+2(modb)))+ x3m+3 =x3m+1 ⋅x3m+2+ x3m+3 = a + a

Что и требовалось доказать.

Наконец, рассмотрим последовательность ${x3n}$ . В силу доказанного выше, если $b=1$ , то все члены последовательности ${x3n}$ равны $a$ , а если $b> 1$ , то

x = x ⋅0+ x =x ⋅x +x = a2+a, 3n+3 3n+1 3n+3 3n+1 3n+2 3n+3

начиная с $n = ⌈logba⌉,$ следовательно, стабильное значение последовательности ${x3n}$ равно $a2+a.$

Ответ:

Последовательность ${x } 3n+1$ стабилизируется на $a$ при $b =1;$ ${x } 3n+2$ стабилизируется на $a$ при $b= 1$ и на $0$ при $b> 1;$ ${x } 3n$ стабилизируется на $a$ при $b= 1,$ начиная с $n= 1,$ и на $2 a + a$ при $b> 1,$ начиная с $n = ⌈logba⌉.$

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

Задача 6#74915

Олег и Оливер гоняют на велосипедах с одинаковыми угловыми скоростями: Оливер — по круговой траектории $𝒜,$ а Олег — по круговой траектории $𝒯$ в два раза меньшего радиуса, причем они стартуют с двух ближайших точек окружностей и круг Олега лежит внутри круга Оливера. По окружности $𝒯$ также движутся два помощника, поддерживающих экран (т.е. хорду с концами в точках, в которых расположены помощники) так, что расстояние от каждого из них до Олега всегда такое же, как и расстояние от Олега до Оливера. Докажите, что на протяжении всей гонки экран касается некоторой фиксированной окружности.

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

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

Подсказка 1

Обозначим за O,V,X и Y Олега, Оливера и двух помощников соответственно. Если нарисовать рисунок, то от нас явно спрятали какую-то известную и хорошую "картинку", посмотрите на равные отрезки, которые нам даны и на окружность 𝒯.

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Да это же центр нашей искомой окружности, ещё не совсем, но можно попробовать это доказать! Мы уже знаем, что она точно касается экрана и её центр не меняется, остаётся показать, что её радиус тоже фиксирован, а какой факт связывает точку, окружность и радиус?

Подсказка 5

Можно использовать степень точки S относительно 𝒯, останется только "перекинуть" равные отрезки так, чтобы остались только фиксированные величины (из исходной "картинки") и радиус окружности с центром в S.

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

Обозначим за $O,V,X$ и $Y$ Олега, Оливера и двух помощников соответственно, за $S$ — центр положительной гомотетии окружностей $𝒯$ и $𝒜.$ Из условия следует, что прямая $V O$ всегда проходит через $S,$ причем, так как радиусы окружностей отличаются в два раза, отрезок $SV$ делится точкой $O$ пополам. Отметим точку $R ⁄= O$ — пересечение луча $OS$ с $𝒯.$ Поскольку равные хорды стягивают равные меньшие дуги, точка $O$ — середина дуги $XOY,$ то есть прямая $RO$ содержит внутреннюю биссектрису треугольника $XRY,$ а еще $OS = OV =OX =OY.$ По лемме о трезубце это означает, что точка $S$ является центром вписанной окружности треугольника $XRY$ $($ обозначим эту окружность за $ω).$

$PIC$

Покажем, что $ω$ является искомой окружностью. Она касается отрезка $XY$ в силу построения, поэтому достаточно проверить, что она не зависит от времени. Как показано выше, центр $ω$ — это $S,$ обозначим ее радиус за $r$ . Также обозначим за $d$ расстояние между центрами $ω$ и $𝒯,$ а за $R$ — постоянный радиус $𝒯.$

Посчитаем степень точки $S$ относительно $𝒯$ двумя способами:

d2− r2 = −RO ⋅SO = −RO ⋅OX =− RO⋅2R sin∠XRO = −2Rr

Величины $d$ и $R$ не зависят от времени, поэтому $r$ также от него не зависит, следовательно, окружность $ω$ имеет постоянный центр и радиус, что и требовалось доказать.

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

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