Тема ИТМО (Открытка)

ИТМО - задания по годам → .10 ИТМО 2024

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

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

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

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

Подтемы раздела итмо (открытка)

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

ИТМО 2015 и ранее

ИТМО 2016

ИТМО 2017

ИТМО 2018

ИТМО 2019

ИТМО 2020

ИТМО 2021

ИТМО 2022

ИТМО 2023

ИТМО 2024

ИТМО 2025

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

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

Задача 1#82286

Дан многочлен $P(x)$ степени $22$ . Известно, что у производной многочлена $P2(x)$ ровно $36$ различных вещественных корней. Какое наибольшее число различных вещественных корней может быть у многочлена $P (x)$ ?

Источники: ИТМО-2024, 11.1 (см. olymp.itmo.ru)

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

Подсказка 1

Нужно взять производную от P^2(x). Она равна 2P(x)P’(x). Что вы можете сказать про корни производной, зная корни многочлена?

Подсказка 2

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

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

Производная многочлена $P2(x)$ равна

( 2 )′ ′ P (x) = 2P (x)P (x)

Видно, что 36 корней этого выражения являются корнями многочлена $P(x)$ или его производной (могут быть одновременно корнями и многочлена, и производной).

По теореме Ролля между каждыми двумя корнями многочлена находится корень производной, не являющийся при этом корнем многочлена. Поэтому если у многочлена $P(x)$ хотя бы 19 корней, то у его производной хотя бы 18 отличных от этих 19 корней. Так что суммарно уже хотя бы $18+19= 37$ различных корней, а это уже больше 36.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма (доказывать на олимпиаде не требовалось): Если число $a$ является корнем многочлена $P(x)$ кратности $k,$ то для производной $′ P (x)$ число $a$ является корнем кратности $k− 1.$

______________________________________________________________________________________________________________________________________________________

Пример на 18 корней строится так: рассмотрим многочлен

P0(x)= x5(x− 1)...(x − 13)(x− 14)(x− 15)(x− 16)(x − 17)

У него и у его производной 18 корней, но есть общий (только $x= 0$ общий по лемме, оставшиеся 17 корней находятся между корнями $P (x)$ по теореме Ролля). Тогда у $′ 2P0(x)P0(x)$ 35 корней.

Но при достаточно маленьком $𝜀> 0$ (можно взять конкретное $𝜀 =0.1$ ) многочлен $P(x)= P0(x)+𝜀$ будет иметь так же 18 корней и такую же производную, но $′ 2P (x)P (x)$ будет иметь уже 36 корней за счёт того, что $x= 0$ перестанеть являться корнем $P (x)$ .

Ответ:

$18$

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

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

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

Задача 2#82288

Натуральные делители натурального числа $n$ занумеровали по возрастанию: $d = 1, d ,...,d = n 1 2 k$ . Оказалось, что $d =120 18$ . Какое наименьшее значение может принимать число $n$ ?

Источники: ИТМО-2024, 11.3 (см. olymp.itmo.ru)

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

Подсказка 1

Первое, что хочется сделать, это разложить 120 на множители. Получается, что все его 16 делителей будут и делителями исходного числа. А что будет, если наше исходное число будет делится, например, на большую степень двойки?

Подсказка 2

Давайте посмотрим. Если n делится на 2^4, то к делителям n прибавится ещё 3 делителя, меньшие 120. Получается, что 120 не будет восемнадцатым делителем. Противоречие. Аналогично рассматривая 3 и 5, может ли n делится на их большие степени? Какой вывод из этого можно сделать?

Подсказка 3

Да, получаем и там аналогичное противоречие. Значит, у n есть простой делитель p, кроме 2, 3 и 5. Если мы сможем оценить его, то задача решена. Нельзя ли почти с помощью почти аналогичного противоречия получить оценку на p?

Подсказка 4

Верно, если у числа будут делители p, 2p и 3p, меньшие 120, то получается снова, что 120 минимум девятнадцатый делитель. Осталось только найти наименьший простой делитель, больший 40, посчитать ответ, и победа!

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

У числа $120 =23⋅5⋅3$ шестнадцать делителей и все они являются делителями числа $n$ . Если $n$ делится на $24$ , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если $n$ делится на $2 3$ , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если $n$ делится на $2 5$ , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, $n$ делится на какое-то простое число $p$ , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа $p,2p$ и $3p$ являются делителями $n$ , меньшими 120 , и мы опять получаем слишком много делителей. Значит, $p$ хотя бы 41 , то есть $n≥ 120⋅41$ . Заметим, что это число нас как раз устраивает.

Ответ: 4920

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

Задача 3#82289

Клетчатый куб $9× 9× 9$ состоит из ячеек, представляющих из себя единичные кубики. 361 ячейка закрашена. Докажите, что в каком-то кубике $2× 2×2$ закрашено хотя бы четыре ячейки.

Источники: ИТМО-2024, 11.4 (см. olymp.itmo.ru)

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

Подсказка 1

Дан куб со стороной 9, а надо понять что-то про кубики со стороной 2. Конечно, неудобно, что большой куб ровно не разбиваются на маленькие. Но мы можем попробовать разбить на кубики 2*2*2 хотя-бы ту часть куба, которую возможно, и применить для нее предположение, противоположное вопросу задачи.

Подсказка 2

Но у нас остается еще часть большого куба, не разбитая на кубы 2*2*2. Эту часть тоже можно как-то разбить хорошо (удобно, что 4 ячейки укладываются в квадратик 2*2) и понять, какое максимальное кол-во закрашенных ячеек может быть, если в каждом кубике 2*2*2 их не более 3!

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

Вырежем из нашего куба куб $8× 8×8$ и разобьём его на 64 куба $2×2 ×2$ .

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

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов $2×2$ , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более $3× 16× 3=144$ .

У нас остались не рассмотренными 25 ячеек, образующих три ребра исходного куба, сходящиеся в одной вершине. Среди них закрашены не более 24, так как общая ячейка трёх этих рёбер и три её соседних лежат в одном кубике $2× 2× 2$ , значит, среди этих четырёх ячеек не более трёх закрашенных.

Таким образом, мы получаем максимум $192+144+ 24= 360$ закрашенных ячеек, что противоречит условию задачи. Значит, наше предположение было неверно.

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

Задача 4#82290

Произведение чисел $a,b,c,d,$ не меньших $2 ,$ составляет $2k+3.$ Найдите наибольшее значение выражения

logcdab+logbdac+ logbcad +logadbc+ logacbd+ logabcd.

Источники: ИТМО-2024, 11.5 (см. olymp.itmo.ru)

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

Подсказка 1

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

Подсказка 2

То, что произведение a, b, c, d — это степень двойки, и то, что каждая из переменных не меньше 2, намекает, что хотелось бы использовать 2 в искомом выражении. Поэтому попробуйте сделать замену вида х = log₂a, ...

Подсказка 3

Полученное выражение — сумма дробей — уже лучше логарифмов. Но как же теперь её оценить? Обратите внимание, что изначальное условие на произведение переменных превратилось в условие на сумму переменных из замены. Какой метод в неравенствах есть, когда фиксирована сумма переменных?

Подсказка 4

Метод Штурма! Часто смотрят на то, когда выражение больше: когда переменные равны или когда одна переменная принимает максимально возможное значение, а другая минимальное. Попробуйте это выяснить на примере двух переменных.

Подсказка 5

Возьмите две переменных с той же суммой, но большей разностью: из x,y сделаем y`=1, x`=x+y-1. Аналогично проделайте для всех четырёх переменных замены. Отсюда и получится искомая оценка!

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

После замены

x= log2a,y =log2b,z = log2c,t=log2d

условие, что исходные числа не меньше $2,$ превращается в

x≥ 1, y ≥ 1, z ≥ 1, t≥ 1,

а условие на произведение превращается в

x+ y+z +t= k+ 3 .

Искомое выражение по формуле перехода и свойствам логарифмов равно

x-+y +-z+t + x+-z+ y+-t+ x+-t+ y+-z z +t x +y y+ t x+ z y+ z x+ t

Воспользуемся методом Штурма. Пусть имеется какое-то значение искомого выражения при удовлетворяющих условиям выше $x ≥y ≥z ≥ t$ (не умаляя общности, переменные можно переименовать для упорядочивания). Заменим два числа $x,y$ на числа $x′ = x+ y− 1≥x,y′ = 1≤ y$ с такой же суммой $x′+ y′ =x +y$ и не меньшей разностью $x′− y′ =x +y− 2≥ x− y ≥ 0 (2y ≥ 2).$ Тогда в искомом выражении сумма дробей

x+y-+ z+-t z+t x+ y

не изменится, а сумма дробей

x+-z+ y+-z= x2+-x(z+t)+zt+-y2+-y(z+-t)+-zt= y+ t x+ t xy +t(x +y)+ t2

(x+ y)2∕2+(x− y)2∕2+ (x +y)(z +t)+2zt = --(x+-y)2∕4−-(x-− y)2∕4-+t(x-+y)+-t2--

и аналогичная ей (с точностью до перестановки $z,t$ ) сумма дробей

x+-t+ y+-t y+z x+ z

не уменьшатся, так как после приведения к общему знаменателю у получившейся дроби числитель увеличивается при увеличении $(x− y)2,$ а знаменатель уменьшается при увеличении $(x− y)2.$

Такими преобразованиями можно превратить три наименьших числа из $x,y,z,t$ в единицу, а наибольшее — в $k,$ при этом наше выражение будет увеличиваться (точнее, заведомо не уменьшаться). Итак, максимальное значение выражения равно

k+-1+ 1+-1+ k+-1+ 1+-1+ k-+1 + 1-+1 = 3(k+-1)+-6-- 1+ 1 k+ 1 1+ 1 k+ 1 1 +1 k +1 2 k+ 1.

Ответ:

$3(k+-1)+-6-- 2 k+ 1$

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

Задача 5#82291

Окружности $S 1$ и $S 2$ находятся внутри трапеции $ABCD$ , касаясь друг друга, оснований трапеции, и каждая — своей боковой стороны. Лучи $AB$ и $DC$ пересекаются в точке $K$ . Оказалось, что радиус вписанной окружности треугольника $BCK$ равен радиусу окружности $S1$ и равен $r.$ Также известно, что $BC = x$ . Найдите площадь треугольника $ADK.$

Источники: ИТМО-2024, 11.6 (см. olymp.itmo.ru)

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

Подсказка 1

Для начала нужно заметить, что радиусы двух окружностей S1 и S2 равны (доказать этот факт не составит труда). После этого надо вписать окружность, которая является вписанной для BCK, в трапецию. Далее можно отметить все точки касания, равные углы и, может быть, заметить какие-то равенства.

Подсказка 2

После того, как мы отметили все равные отрезки, останется выразить высоту треугольника АDK через известные нам величины и найти площадь.

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

Радиусы $S 1$ и $S 2$ равны друг другу и высоте трапеции. Из условия про пересечение лучей следует, что $BC$ — меньшее основание.

Проведём вторую касательную к вписанной окружности треугольника $BCK$ параллельную основаниям трапеции. Обозначим за $X$ и $Y$ точки пересечения этой касательной с отрезками $BK$ и $CK.BXY C$ — трапеция.

Точки касания окружностей и оснований трапеции образуют квадрат со стороной $2r$ . Если вырезать этот квадрат из трапеции и склеить оставшиеся части между собой, получится трапеция, равная $BXY C$ .

Более точно, обозначим точки касания окружностей $S1$ и $S2$ с основаниями трапеции $ABCD$ : пусть $M$ и $N$ лежат на $BC$ ( $M$ ближе к $B$ ), $P$ и $Q$ лежат на $AD$ ( $P$ ближе к $A$ ). Кроме того, пусть $U,V,W,Z$ — точки касания вписанной окружности $BCK$ с $XY,BC,BK,CK$ соответственно. Кроме того, пусть $S$ и $T$ — точки касания окружностей $S1$ и $S2$ с боковыми сторонами трапеции, $O1,O2$ и $O$ — центры окружностей $S1,S2$ и вписанной окружности треугольника $BCK$ .

$PIC$

Рассмотрим четырёхугольники $SBMO1$ и $W XUO :$

$∠SBM = ∠W XU,$ как соответственные. $∠O1SB,∠BMO1, ∠OW X$ , $∠XUO$ прямые.

Значит оставшиеся углы, $∠MO1S$ и $∠UOW$ также равны. Значит, треугольники $MO1S$ и $UOW$ равны. Следовательно, треугольники $SBM$ и $W XU$ также равны, а значит четырёхугольники $SBMO1$ и $W XUO$ равны. Аналогично

SAP O1 = WBV O,TDQO2 = ZCV O,TCNO2 = ZYUO

Значит,

BC = BV +CV = AP + QD =AD − PQ = AD − 2r

AD =BC + 2r= x+ 2r

Пусть $h$ — длина высоты треугольника $BCK$ , проведённой из точки $K$ . Тогда длина высоты треугольника $ADK$ , проведённой из точки $K$ равна $h+ 2r$ . Значит, коэффициент подобия треугольников $ADK$ и $BCK$ с одной стороны равен $h+2r- h$ , а с другой $AD- x+2r BC = x$ , откуда $h= x$ . Значит, площадь треугольника $ADK$ равна

AD ⋅(h+2r) (x+ 2r)2 ----2-----= ---2---

Ответ:

$(x+-2r)2 2$

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

Задача 6#82292

Сфера $S$ касается основания $ABC$ тетраэдра $ABCD$ в точке $H$ и проходит через вершину $D$ . Рёбра $AD,BD$ и $CD$ эта сфера пересекает в точках $A1,B1$ и $C1$ . Центр описанной окружности треугольника $A1B1C1$ лежит на отрезке $DH$ . Радиус сферы $S$ равен $R$ .

Пусть $V$ - объём тетраэдра $ABCD$ , а $V1$ - объём тетраэдра $A1B1C1D$ . Какое наибольшее значение может принимать $V ⋅V1?$

Источники: ИТМО-2024, 11.7 (см. olymp.itmo.ru)

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

Пусть $H 1$ — центр описанной окружности треугольника $A B C 1 11$ , лежащий на $DH,O$ — центр сферы. Очевидно, $O$ — середина $DH$ . Так как точки $A1,B1$ и $C1$ лежат на сфере, $OH1$ перпендикулярно плоскости $A1B1C1$ . С другой стороны, $OH1$ и $DH$ — это одна и та же прямая, а $DH$ перпендикулярна плоскости $ABC$ . Значит, плоскости $ABC$ и $A1B1C1$ параллельны, а тетраэдры $ABCD$ и $A1B1C1D$ подобны.

$PIC$

Пусть $h$ — длина $DH1$ , то есть высота маленького тетраэдра. Высота большого тетраэдра равна $2R$ , а коэффициент их подобия $− 2Rh$ .

$OH1A$ - прямоугольный треугольник с прямым углом $H1,OH1 = |R − h|,OA1 = R$ , значит, радиус описанной окружности треугольника $A1B1C1$ , то есть $OH1$ , равен

r= ∘R2-− (R-− h)2 = ∘2Rh-− h2

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

3√3r2 4

Значит, объемы тетраэдров составляют

h 3√3r2 √3hr2 √3h(2Rh− h2) √3h2(2R − h) V1 = 3 ⋅-4- = -4---= -----4------= -----4-----

( )3 √- √- V = 2R-- ⋅V1 = 8R3 ⋅-3h2(2R-− h)= 2-3R3(2R−-h), h h3 4 h

а их произведение равно

3R3h(2R-−-h)2 2

Чтобы максимизировать эту величину, достаточно максимизировать $2 f(h)= h(2R − h) .$

f′(h) =(2R− h)2 − 2h(2R − h)=(2R− h)(2R − 3h)

′ 2R f = 0 ⇐⇒ h= 2R или h= -3-

В первой точке достигается минимум, равный нулю, а во второй — максимум. Подставив $2R h= -3$ в формулу для объёма, получим

16R6 max(V V1) = 9

Ответ:

$16R6 9$

Курсы

Всё необходимое для достижения цели

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

Задача 7#82293

100 человек пришли на представление в шляпах. Фокусник поменял местами их шляпы. После этого каждую минуту каждый человек находил свою шляпу и передавал тому, у кого эта шляпа в данный момент находилась, ту шляпу, которая в этот момент была у него самого. (Если на каком-то шаге у человека $A$ оказывается шляпа, принадлежащая человеку $B$ , а у человека $C$ оказывается шляпа, принадлежащая человеку самому $A$ , то на следующем шаге у $C$ оказывается шляпа, принадлежащая $B$ ).

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

Источники: ИТМО-2024, 11.8 (см. olymp.itmo.ru)

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

Подсказка 1

Условие про то, как передвигаются шляпы достаточно сложное, поэтому, чтобы хорошо его понять, нужно самому подвигать шляпы на каком-то количестве человек. Давайте рассмотрим какого-то человека А₀, так как мы сами вводим обозначения, то давайте изначально его шляпа была у А₁. Тогда человека, держащего шляпу А₁, назовём А₂ и так далее. В какой момент цепочка А₀- А₁-А₂ остановится? Обязательно поймите, почему это точно произойдёт.

Подсказка 2

Цепочка остановится в момент, когда шляпа какого-то Аₙ₋₁ окажется у Aₖ, которого мы уже записывала в нее. Тогда чему может быть равно k?

Подсказка 3

Через минуту шляпа А₀ окажется у того, кто держал раньше шляпу А₁, то есть у А₂, шляпа А₁ будет у А₃. Тогда можно сделать вывод, что для каждого k шляпа Aₖ через минуту окажется у Aₖ₊₂.

Подсказка 4

Через m минут шляпа Aₖ будет находиться у человека с номером k + 2ᵐ. Тогда при каком количестве человек шляпа сможет вернутся к исходному владельцу? Воспользуйтесь тем, что Aₖ = Аₙ₊ₖ.

Подсказка 5

Шляпа может вернуться к исходном владельцу только в случае, если количество человек в цикле является степенью двойки! По условию фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам. Это значит, что все 100 человек разобьются на некоторое количество циклов (цикл из одного человека тоже может быть). Но мы уже получили условие на длины циклов. Тогда какая может быть наибольшая, учитывая ограничение в 100 человек?

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

Рассмотрим некоторого человека, назовём его $A 0$ . Пусть его шляпа изначально оказалась у какого-то $A 1$ , шляпа $A 1$ оказалась у $A 2$ , и т.д. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то $An−1$ его шляпа окажется у какого-то $Ak$ , который был уже нами пронумерован ранее. При этом это может быть только $A0$ , т.к. про всех остальных мы уже знаем, откуда взялись находящиеся у них шляпы.

Значит, шляпа $An−1$ в начале представления оказалась у $A0$ и мы получили так называемый цикл из $n$ человек. Для удобства будем считать, что $An =A0,An+1 =A1$ и т.д., чтобы иметь возможность говорить, что каждый человек с номером $k$ передал свою шляпу человеку с номером $k+1$ (то есть, мы на самом деле нумеруем людей остатками (классами вычетов) при делении на $n$ ).

После того, как джентльмены передадут свои шляпы, шляпа $A0$ окажется у того, у кого раньше была шляпа $A1$ , то есть у $A2$ , шляпа $A1$ окажется у $A3$ и т.д. Шляпа каждого $Ak$ окажется у $Ak+2$ . После второй передачи шляпа каждого $Ak$ окажется у $Ak+4$ и т.д. Через $m$ минут шляпа $Ak$ окажется у $Ak+2m$ .

Если это тот же человек, что и $Ak$ , разность их номеров, то есть $2m$ , должна делится на $n$ . Значит, шляпа может вернуться к исходном владельцу, только если количество человек в цикле является степенью двойки. При этом фокусник хочет, чтобы был цикл как можно большей длины.

Самая большая степень двойки, не превосходящая 100, это $64= 26$ . Фокусник в начале должен разбить пришедших на представление на циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).

Ответ: 6

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

Задача 8#91147

Последовательность ${a } n$ задана рекуррентным соотношением

an = an−1 +an−2− an−3+3

и начальными условиями $a0 = 1,a2 =5.$ Чему может быть равно $a6?$

Источники: ИТМО-2024, 11.2 (см. olymp.itmo.ru)

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

Подсказка 1

Что первое хочется сделать, увидев рекуррентную формулу? Попробовать подставить что-то вместо n. Например, взять n-1 и посмотреть, что получится. В задаче же у нас спрашивают про чётный член. Тогда в теории надо как-то избавиться от членов вида n-1 и n-3 в формуле. Посмотрев на формулы для n и n-1, что можно попробовать сделать?

Подсказка 2

Давайте сложим две формулы, тогда останутся только члены с номерами n, n-2 и n-4. Теперь, записав полученное выражение как разность членов n, n-2 и n-2, n-4, можем найти формулу для разности 2k и 2(k-1) члена, через суммирование таких выражений. Как же теперь можно найти формулу для 2k-ого члена?

Подсказка 3

Верно, сложим аналогично выражения для всех k от 1 до 3. Тогда слагаемые буду сокращаться и мы сможем выразить 6-ый член. Победа!

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

Перепишем рекуррентную формулу: