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

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

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

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

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

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

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

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

ИТМО 2015 и ранее

ИТМО 2016

ИТМО 2017

ИТМО 2018

ИТМО 2019

ИТМО 2020

ИТМО 2021

ИТМО 2022

ИТМО 2023

ИТМО 2024

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

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

Задача 1#82286

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

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

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

Производная многочлена $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)

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

У числа $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)

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

Вырежем из нашего куба куб $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)

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

После замены

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)

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

Радиусы $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)

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

Рассмотрим некоторого человека, назовём его $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 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).