Рассылка решений заочных туров олимпиад по математике

Подписывайтесь на нашу рассылку решений заочных туров всех олимпиад по математике: Ломоносов, Покори Воробьевы горы, Высшая проба, Физтех 2018 и другие перечневые олимпиады.

Открытая олимпиада школьников по математике 2016-2017 (ИТМО) / Задания и решения отборочного этапа


  • Сезон олимпиад 2016-2017 открыт!
    Идет запись на наши курсы подготовки к олимпиадам по математике с гарантированным результатом.
    image
    1. Индивидуальные занятия и консультации.
    2. Помощь в прохождении заочных туров олимпиад. Одна олимпиада 1-5 тыс. руб.
    3. Помощь эксперта на очных турах олимпиад. Одна олимпиада от 30 тыс. руб.
    4. Гарантия успешного результата (курсы ведутся пятый сезон).

    Стоимость курсов от 3000 до 25000 руб. в месяц. Стандартный курс - 10000 руб. в месяц. Длительность курсов - 6 месяцев.
    В составе стандартного курса заочные туры 10 олимпиад и очные туры 2 олимпиад.
    Посмотреть тарифные планы и подробную информацию по курсам подготовки.


    Открытая олимпиада школьников по математике 2016-2017 вошла в перечень олимпиад этого года.
    Уровень - 2.

    Отборочный этап


    Отборочный этап проводится в дистанционной форме с 20 ноября по 12 декабря.
    Предлагается 10 заданий различной сложности и разного веса (от 1 до 4 баллов). Общая сумма баллов - 29.
    Предполгаемый проходной - 15+.
    Ниже выложены решения одного из вариантов + алгоритмы общих решений, по которым легко получить ответ своего варианта задания.
    Длительность отборочного этапа - 3 часа, время начала выполнения работы определяет сам абитуриент.
    Подробные решения не требуются, достаточно ответов, но ответы должны быть введены в соответствии с инструкциями (по каждому номеру есть своя инструкция по вводу ответа).
    Заметим, что сложность задач не совсем соответствует баллам за задачи. Начинайте с самых простых задач.

    Открытая олимпиада школьников по математике 2016-2017. Заключительный этап.


    Заключительный этап в очной форме будет проведен 20 марта (предварительная дата).
    Города проведения очного тура:
    Москва, Санкт-Петербург, Екатеринбург, Иркутск, Красноярск, Челябинск, Саратов, Саранск, Белогород.
    Тема будет дополняться при поступлении новой информации.
  • Задача №1 (2 балла).
    Три высоты тетраэдра больше радиуса его вписанной сферы в `k, n` и `m` раз соответственно. Во сколько раз четвёртая высота больше радиуса вписанной сферы?

    Решение:
    `r` - радиус вписанной сферы.
    `h_(1,2,3,4)=kr, nr, mr, xr` - высоты.
    `S_(1,2,3,4)` - площади граней.
    Требуется найти `x`.
    `V=1/3h_iS_i=1/3krS_1=1/3nrS_2=1/3mrS_3=1/3xrS_4`,
    `S_1=(3V)/(kr), S_2=(3V)/(nr), S_3=(3V)/(mr), S_4=(3V)/(xr)`.
    С другой стороны, `V=1/3r(S_1+S_2+S_3+S_4)`.
    `V=1/3r*(3V)/r*(1/k+1/n+1/m+1/x)`,
    `1/k+1/n+1/m+1/x=1`,
    `1/x=1-1/k-1/m-1/n`,
    `1/x=(kmn-km-mn-mk)/(kmn)`,
    `x=(kmn)/(kmn-km-mn-mk)`.
    Надо подставить свои значения `k,m,n`, получить дробь, довести ее до несокращаемого вида и записать в ответ.
  • Задача №2 (2 балла).
    Калькулятор АЧ-2016 может выполнять две операции: извлечение кубического корня и взятие тангенса. Изначально в калькулятор было введено число `2^(-243)`. За какое наименьшее число операций из него можно получить число, большее `1`?

    Решение:
    `243=3^5`.
    `(2^(-243))^(1/3)=2^(-81)`,
    `(2^(-81))^(1/3)=2^(-27)`,
    `(2^(-27))^(1/3)=2^(-9)`,
    `(2^(-9))^(1/3)=2^(-3)`,
    `(2^(-3))^(1/3)=2^(-1)`,
    `(2^(-1))^(1/3)=2^(-1/3)`.
    `tan(2^(-1/3)) ~~ 1,0167>1`.
    Всего потребовалось 7 операций.

    В других задачах следующие формулировки: дается число вида `n^(-k)`, где `k` является степенью `2, 3` и т.д. Операции - извлечение квадратного (кубического и т.д.) корня + взятие тригонометрической функции (тангенс, арксинус и т.д.).
    Действуем следующим образом:
    Например, `k=2^m`, а операция - извлечение квадратного корня.
    Извлекаем квадратный корень `m` раз, получаем число `n^(-1)`.
    На сайте http://www.wolframalpha.com считаем значение данной в условии тригонометрической функции в точке `n^(-1)`. Если это значение меньше `1`, то продолжаем первую операцию.
    `(m+1)`-ая операция извлечения корня, получаем число `n^(-1/2)`. Снова проверяем значение тригонометрической функции уже в точке `n^(-1/2)`. Если больше `1`, то всего `m+2` операций. Если меньше, то продолжаем первую операцию.
    `(m+2)`-ая операция извлечения корня, получаем число `n^(-1/4)`. И т.д.
    В разных вариантов ответ равен `m+2, m+3, m+4`. Возможны и другие значения (как меньшие, так и большие).
  • Задача №3 (2 балла).
    При каком наибольшем `a` множество значений функции `sqrt(a(sqrt3sinpix+cospix))` целиком содержится в области её определения?

    Решение:
    Пусть `f(x)=sqrt(a(sqrt3sinpix+cospix))`.
    `sqrt3sinpix+cospix=2(sqrt3/2sinpix+1/2cospix)=`
    `=2(cos(pi/6)sinpix+sin(pi/6)cospix)=2sin(pix+pi/6) in [-2;2]`.
    Тогда область значений `Ef=[0;sqrt(2|a|)]`.
    Найдем область определения:
    `asin(pix+pi/6)>=0`.
    `a=0` - подходит.
    `a>0 => sin(pix+pi/6)>=0 => -1/6+2k<=x<=5/6+2k, k in ZZ`.
    `a<0 => sin(pix+pi/6)<=0 => 5/6+2n<=x<=11/6+2n, n in ZZ`.
    Случай 1: `a>0 => x in ...uu[-13/6;-7/6]uu[-1/6;5/6]uu[11/6;17/6]uu...`
    `Ef in Df iff sqrt(2|a|)<=5/6 => 2|a|<=25/36 => |a|=a<=25/72`.
    Случай 2: `a<0 => x in ...uu[-7/6;-1/6]uu[5/6;11/6]uu...`
    В таком случае `Ef` не может целиком содержаться в `Df`.
    Случай 3: `a=0 => Df-=RR => Ef in Df`.
    Итак, `a_max=25/72`.

    Ответ: `25/72`.
    Если требуется найти наименьшее значение, то оно равно `0`.
  • Задача №4 (3 балла).
    Кубический многочлен `p(x)` со старшим коэффициентом `1` таков, что `p'(1) = p(0), p'(2) = p(1), p'(3) = p(2)`. Найдите коэффициент при `x` в многочлене `p(x)`.

    Решение:
    `p(x)=x^3+ax^2+bx+c`,
    `p'(x)=3x^2+2ax+b`,
    `p'(1)=3+2a+b, p'(2)=12+4a+b, p'(3)=27+6a+b`,
    `p(0)=c, p(1)=1+a+b+c, p(2)=8+4a+2b+c`.
    Из первого равенства `p'(1)=p(0)` следует, что `c=3+2a+b`.
    `p(1)=4+3a+2b, p(2)=11+6a+3b`.
    `12+4a+b=4+3a+2b => a=b+8`,
    `27+6a+b=11+6a+3b => b=8, a=0, c=11`.
    `p(x)=x^3+8x+11`.

    Ответ: `8`.
    Если спрашивается иной коэффициент (при `x^2` или свободный член), в ответе записываем другое число.
    Если даются другие равенства, то получаем другие уравнения и аналогично решаем.
    Быстро решить систему из трех уравнений с тремя неизвестными можно на сайте http://www.wolframalpha.com
    Вводим, например, (c=3+2a+b, 1+a+b+c=12+4a+b, 8+4a+2b+c=27+6a+b), получаем все решения.
  • Задача №5 (3 балла).
    В стране есть `n` городов, некоторые из которых соединены почтовыми рейсами. Чтобы письмо дошло из одного города в другой, на него нужно наклеить столько марок, сколько рейсов для это требуется (используется маршрут, требующий наименьшего количества рейсов). Известно, что даже если два города не соединены рейсом, послать письмо из одного в другой всегда возможно.
    Под Новый Год мэры всех городов послали друг другу поздравительные письма. Какое наибольшее количество марок могло им всем потребоваться?

    Решение:
    На языке теории графов задача выглядит так: дан простой связный граф с `n` вершинами. Для каждой пары вершин определено расстояние между ними как длина кратчайшего соединяющего их пути. Далее подсчитывается удвоенная сумма всех попарных расстояний. Это и будет общее число марок. Нужно найти максимальное значение для такой величины.
    Если граф не является деревом, то он имеет циклический подграф. При удалении любого ребра, входящего в простой цикл, попарные расстояния между вершинами не увеличиваются, и легко видеть, что общая сумма даже строго уменьшается (расстояния `1` между вершинами, для которых удалили соединяющее ребро, уже не будет). Поэтому оптимум будет достигаться на одном из деревьев.

    Докажем, что таким свойством обладает линейный граф, и только он (когда все вершины друг с другом соединены по цепочке: `1`-я со `2`-й, `2`-я с `3`-й, предпоследняя с последней). Для линейного графа с `n` вершинами общая сумма попарных расстояний (не удвоенная) равна `((n−1)n(n+1))/6`, что легко проверятся по индукции. Когда добавляется новая `(n+1)`-я вершина с краю, то сумма расстояний от неё до остальных точек равна `1+2+...+n=(n(n+1))/2`, и после прибавления к предыдущей величине получается следующее значение вида `C_(n+2)^3`.

    Теперь проверим оптимальность, также рассуждая по индукции. База здесь очевидна, потому что при `n<=3` кроме линейных графов других деревьев не бывает. Пусть для `n>=3` утверждение считается доказанным. В дереве с `n+1` вершиной имеется висячая вершина. Удалим её вместе с инцидентным ей ребром. У оставшегося графа сумма попарных расстояний не превосходит `((n−1)n(n+1))/6` по предположению. Добавим к ней расстояния от удалённой вершины до всех остальных. Упорядочим их по неубыванию: `d_1<=d_2<=...<=d_n`. Ясно, что `d_1=1` (расстояние от висячей вершины до ближайшей). Далее `d_2<=2, d_3<=3, ... , d_n<=n`, поскольку "пробела" между соседними значениями величиной больше `1` быть не может. Докажем это формально.
    Допустим, что `d_(i+1)−d_i>1`. Рассмотрим кратчайший путь длиной `d_(i+1)` до висячей вершины. Следующая вершина на этом пути после начальной находится от висячей на расстоянии `d_(i+1)−1`, то есть строго между значениями `d_i` и `d_(i+1)`, а таких вершин у нас нет.
    Таким образом, при добавлении новой вершины к предыдущей сумме добавляется не более `1+2+...+n=(n(n+1))/2`, что приводит к нужной оценке. То, что максимум достигается именно на линейном графе, также нетрудно извлечь из доказательства.

    Итого марок будет нужно `2*((n-1)n(n+1))/6=((n-1)n(n+1))/3`.
    Подставляем свое значение `n`, получаем ответ.
  • Задача №6 (3 балла).
    Коля взял дробно-линейную функцию `(kax+nb)/(kcx+nd)`, где `a, b, c, d` — различные по абсолютной величине числа, и сложил её со всеми оставшимися `23` функциями, которые получаются из неё перестановкой чисел `a, b, c, d`. Найдите корень суммы всех этих фунций, не зависящий от чисел `a, b, c, d`.

    Решение:
    Заменим `x` на `n/k*t`:
    `(kax+nb)/(kcx+nd)=(at+b)/(ct+d)`.
    Сгруппируем функции по парам:
    `(at+b)/(ct+d)+(bt+a)/(ct+d)=((a+b)(t+1))/(ct+d)`.
    Тогда сумма всех `24` функций делится на `(t+1)`, следовательно, `t=-1` общий корень суммы всех функций, при этом он не зависит от `a,b,c,d`.
    Докажем, что других таких корней нет.
    Для начала рассмотрим такую аналогию. Пусть у нас имеется сумма несократимых дробей (положительных или отрицательных), знаменатели которых попарно взаимно просты. Тогда сумма таких дробей не может равняться никакому целому числу (в частности, она не будет равна нулю). Действительно, если мы домножим равенство на произведение всех знаменателей кроме одного, то получится сумма одного заведомо не целого и нескольких целых чисел, которая целому числу не равна.
    Пусть теперь `t` - некоторая фиксированная числовая константа. В знаменателях дробей у нас стоят линейные формы от буквенных переменных `a, b, c, d`. Если никакие две формы не пропорциональны, то это аналог взаимной простоты. Суммой таких дробей не может быть никакой многочлен от `a, b, c, d` - в том числе, нулевой. Доказательство по сути такое же: надо домножить на все знаменатели кроме одного, и тогда получится, что некоторое дробное выражение тождественно равно многочлену, чего быть не может.
    Таким образом, среди линейных форм должны быть пропорциональные. Чему может быть пропорциональна форма `at+b`? Только форме с участием тех же переменных, то есть `a+tb`. Но это значит, что коэффициент пропорциональности равен `t`, откуда `t^2=1`. Случай `t=1` невозможен, так как при положительных значениях параметров из условия, сумма окажется положительной. Значит, `t=−1`, что и надо было обосновать.

    Итак, `t=-1 => x=-n/k`.
    Подставляем свои значения `n,k`, получаем ответ.
  • Задача №7 (3 балла).
    Две окружности с центрами в точках `O_1` и `O_2` и радиусами `R` и `r` соответственно пересекаются в точках `A` и `B`. Точка `X` лежит на луче `AB` и такова, что `O_1X = a, AX = b`.
    Найдите расстояние между центрами окружностей.

    Решение:
    `AH=x`.
    Опустим перпендикуляр `O_1H` на `AB`.
    `O_1H^2=R^2-AH^2=R^2-t^2`,
    `O_1H^2=x^2-(AH+AX)^2=a^2-(x+b)^2`.
    `R^2-x^2=a^2-(x+b)^2`,
    `2xb=a^2-R^2`,
    `x=(a^2-R^2)/(2b)`.
    В условии дают такие числа `R,r,a,b`, что всегда выполняется равенство `r=(a^2-R^2)/(2b)`.
    Итак, мы получили, что `AH=x=r`.
    С другой стороны, `AH` - половина хорды `AB`, поэтому `AB` является диаметром второй окружности.
    Тогда `O_1O_2=O_1H=sqrt(R^2-r^2)`.
    Подставляем свои значения `R,r`, получаем ответ.
    Искомое расстояние равно `sqrt(R^2-r^2)`.
  • Задача №8 (3 балла).
    Функия `f(x)` такова, что `f(kx)=c—(f(x))/k`. Найдите площадь подграфика функции
     `f(1 — nx + (n+1)|x|)` на участке от `-1` до `2n+1`.

    Решение:
    `int_(-1)^(2n+1)f(1 — nx + (n+1)|x|)dx=int_(-1)^0f(1-(2n+1)x)dx+int_(0)^(2n+1)f(1+x)dx`.
    `1-(2n+1)x=t => int_(-1)^0f(1-(2n+1)x)dx=int_(1+(2n+1))^1f(t)d((1-t)/(2n+1))=`
    `=1/(2n+1)int_1^(2n+2)f(t)dt`.
    `1+x=t => int_(0)^(2n+1)f(1+x)dx=int_1^(2n+2)f(t)dt`.
    `int_(-1)^(2n+1)f(1 — nx + (n+1)|x|)dx=(1+1/(2n+1))int_1^(2n+2)f(t)dt=`
    `=(2n+2)/(2n+1)int_1^(2n+2)f(t)dt`.
    Пусть `I(a,b)=int_a^bf(t)dt`.
    `I(a,b)=int_(a/k)^(b/k)f(kt)d(kt)=kint_(a/k)^(b/k)(c—(f(x))/k)dt=`
    `=kint_(a/k)^(b/k)cdt-I(a/k,b/k)=c(b-a)-I(a/k,b/k)`.
    Тогда, `I(a,b)=c(b-a)*(1-1/k+1/k^2-1/k^3+...)`,
    `1-1/k+1/k^2-1/k^3+...=1/(1+1/k)=k/(k+1)`,
    `I(a,b)=c*(b-a)*k/(k+1) => f(x)-=(ck)/(k+1)`.
    Найденная функция удовлетворяет функциональному соотношению.
    Тогда, `S=(2n+2)/(2n+1)int_1^(2n+2)f(t)dt=(2n+2)/(2n+1)*(ck)/(k+1)*(2n+2-1)=(ck(2n+2))/(k+1)`.
    Подставляем свои значения `k,c,n`, получаем ответ.
  • Задача №9 (4 балла).
    Найдите последнюю цифру целой части числа `(sqrt37+sqrt35)^(2n)`.

    Решение:
    Пусть `t_1=(sqrt37-sqrt35)^2, t_2=(sqrt37+sqrt35)^2`.
    `t_1*t_2=4, t_1+t_2=2*(37+35)=144`.
    `t_(1,2)` корни квадратного уравнения `t^2-144t+4=0`.
    Это квадратное уравнение является характеристическим уравнением последовательности `a_n=t^n => a_(n+2)=144a_(n+1)-4a_n`.
    Аналогично для последовательности `b_n=t_1^n+t_2^n` получаем `b_(n+2)=144b_(n+1)-4b_n`.
    `b_0=2, b_1=144 => b_n in NN`.
    Из рекуррентного соотношения следует цикличность последних цифр `b_n`: `2,4,8,6,2,4,8,6,...`
    `t_1*t_2=4 => b_n=t_2^n+(4/(t_2))^n`, где `(4/(t_2))^n<1`.
    Тогда `[(t_2)^n]=b_n-1`.
    Последняя цифра целой части числа `(sqrt37+sqrt35)^(2n)=(t_2)^n` равна последней цифре числа `b_n-1`.
    Если `n` дает остаток `0` при делении на `4`, то последняя цифра равна `2-1=1`.
    Если `n` дает остаток `1` при делении на `4`, то последняя цифра равна `4-1=3`.
    Если `n` дает остаток `2` при делении на `4`, то последняя цифра равна `8-1=7`.
    Если `n` дает остаток `3` при делении на `4`, то последняя цифра равна `6-1=5`.
  • Задача №10 (4 балла).
    Куб описан вокруг сферы радиуса `1`. Из одного из центров граней куба проведены векторы ко всем остальным центрам граней и вершинам. У получившихся векторов посчитали скалярные произведения для каждой пары различных векторов, всего `78`  штук. Чему равна сумма этих скалярных произведений?

    Ответ: `76`.

Рассылка решений заочных туров олимпиад по математике