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

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

Очный тур олимпиады школьников СПбГУ 2014-2015 по математике / Задания и решения


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

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



    Олимпиада СПбГУ 2015-2016 - задания и решения отборочного этапа по математике.
    Очный тур олимпиады школьников СПбГУ 2014-2015 по математике. Задания и решения некоторых вариантов.
    Олимпиада школьников СПбГУ по математике. Заключительный этап.
    image
    image
    image
    image
  • Вариант 1. Задача №1.
    В теннисном турнире  участвуют `2^n+4` школьников, где `n` - натуральное число, большее `4`. За победу даётся `1` очко, за поражение - `0` очков. Перед каждым туром пары по жребию составляют из участников, имеющих равное количество очков (те, кому не нашлось пары, пропускают тур). Турнир заканчивается, как только определяется единоличный лидер. Сколько школьников после окончания турнира  наберут по `3` очка?

    Решение:
    `f_m(k)` - кол-во школьников, которые наберут `k` очков после `m`-го тура.
    Например, `f_1(1)=f_1(0)=2^(n-1)+2, f_0(0)=2^n+4`.
    Легко заметить следующие реккурентные соотношения:
    `f_(m+1)(k+1)=1/2f_m(k)+1/2f_m(k+1)`, если `f_m(k), f_m(k+1)` четны.
    `f_(m+1)(k+1)=1/2(f_m(k)-1)+1/2f_m(k+1)`, если `f_m(k)` нечетен, `f_m(k+1)` четен.
    `f_(m+1)(k+1)=1/2f_m(k)+1/2(f_m(k+1)-1)+1`, если наоборот.
    `f_(m+1)(k+1)=1/2(f_m(k)-1)+1/2(f_m(k+1)-1)+1=`
    `=1/2f_m(k)+1/2f_m(k+1)`, если оба нечетны.
    `f_m(m)=2^(n-m), f_m(0)=2^(n-m)+1`.

    После `m` туров школьник мог набрать максимум `m` очков. Также заметим, что кол-во участников, которые набрали максимум очков после `m` туров, равно `2^(n-m)`, т.к. после каждого тура число участников, набравшие максимум баллов уменьшается в два раза или минус один и в два раза.
    Поэтому, через `n` туров ровно один школьник наберет `n` очков, он и станет победителем. Надо найти, чему равно `f_n(3)`.
    `f_2(2)=2^(n-2)+1, f_2(1)=2^(n-1)+2, f_2(0)=2^(n-2)+1`,
    `f_3(3)=2^(n-3), f_3(2)=2^(n-2)+2^(n-3)+2`,
    `f_3(1)=2^(n-2)+1+2^(n-3), f_3(0)=2^(n-3)+1`,
    `f_4(4)=2^(n-4), f_4(3)=2^(n-2)+1, f_4(2)=2^(n-2)+2^(n-3)+1`,
    `f_4(1)=2^(n-2)+1, f_4(0)=2^(n-4)+1`,
    Заметим, что при `m>=4`: `f_m(k)` четно при `k>=4` и нечетно при `k=3,2,1,0`.
    При `m=n` меняется четность первого и последнего выражений.
    Тогда `f_m(k)` всегда нечетно при `m>=4, k<=3` и равно `1/2f_(m-1)(k)+1/2f_(m-1)(k-1)`.
    `f_m(0)=2^(n-m)+1`,
    `f_m(1)=1/2f_(m-1)(1)+1/2f_(m-1)(0)=m*2^(n-m)+1` - можно доказать по индукции.
    `f_m(2)=1/2f_(m-1)(2)+1/2f_(m-1)(1)`.
    Пусть `f_m(2)=g(m)*2^(n-m)+1`:
    `g(m)*2^(n-m)+1=g(m-1)*2^(n-m)+(m-1)*2^(n-m)+1`,
    `g(m)=g(m-1)+m-1=1+2+...+m-1=(m(m-1))/2 =>`
    `=>f_m(2)=(m(m-1))/2*2^(n-m)+1`.
    Аналогично найдем, что `f_m(3)=(m(m-1)(m-2))/6*2^(n-m)+1`.
    Тогда, `f_n(3)=(n(n-1)(n-2))/6+1`.
    Предположу, что есть легкий способ нахождения `f_n(3)`, мы решили намного более общую задачу.

    Ответ: `(n(n-1)(n-2))/6+1`.
  • Вариант 1. Задача №2.
    Найдите наименьшее значение выражения при `a,b>0`
    `(|6a-4b|+|3(a+bsqrt3)+2(asqrt3-b)|)/sqrt(a^2+b^2)`.

    Решение:
    Наше выражение обозначим через `F(a,b)`.
    Пусть `a^2+b^2=c^2 => (a/c)^2+(b/c)^2=1`.
    `F(a,b)=A/B=(A/c)/(B/c)=F(a/c, b/c)`.
    `F` не зависит от `c`, поэтому можем сказать, что `c=1`.
    Тогда существует такой `x in (0;pi/2)`, что `a=sinx, b=cosx`. Учли то, что `a,b>0`.
    `F(x)=|6sinx-4cosx|+|(3+2sqrt3)sinx+(3sqrt3-2)cosx|`.
    Заметим, что `6^2+4^2=52=(3+2sqrt3)^2+(3sqrt3-2)^2`.
    `1/sqrt52*F(x)=|sin(x-alpha)|+|sin(x+beta)|`, где `cosalpha=6/sqrt52, cosbeta=(3+2sqrt3)/sqrt52`.
    `1/sqrt2<6/sqrt52< sqrt3/2<(3+2sqrt3)/sqrt52 => 0< beta< pi/6< alpha< pi/4`.
    `x+beta in (0;pi/2+pi/6) => |sin(x+beta)|=sin(x+beta)`.
    Пусть `x>=alpha => 1/sqrt52*F(x)=sin(x-alpha)+sin(x+beta)=`
    `=2sin(x-1/2alpha+1/2beta)*cos(1/2alpha+1/2beta)`.
    Второй сомножитель константа, `x-1/2alpha+1/2beta in (0;pi/2)`, поэтому минимум будет при минимальном `x=alpha`.
    `F_min=sqrt52*2sin(1/2alpha+1/2beta)*cos(1/2alpha+1/2beta)=`
    `=sqrt52*sin(alpha+beta)`.
    `sin(alpha+beta)=4/sqrt52*(3+2sqrt3)/sqrt52+(3sqrt3-2)/sqrt52*6/sqrt52`.
    `F_min=1/sqrt52*(12+8sqrt3+18sqrt3-12)=(26sqrt3)/sqrt52=sqrt39`.
    Пусть `x<=alpha => 1/sqrt52*F(x)=2cos(x-1/2alpha+1/2beta)*sin(1/2alpha+1/2beta)`.
    Далее все аналогично, получаем, что `F_min=F(alpha)=sqrt39`.

    Ответ: `sqrt39`.
  • Вариант 1. Задача №3.
    Внутри окружности `omega` расположены пересекающиеся в точках `K` и `L` окружности `omega_1` и `omega_2`, касающиеся окружности `omega` в точках `M` и `N`. Оказалось, что точки `K,M,N` лежат на одной прямой. Найдите радиус окружности `omega`, если радиусы окружностей `omega_1` и `omega_2` равны `3` и `5` соответственно.

    Решение:
    Точки `O,O_1,O_2` центры окружностей `omega, omega_1` и `omega_2` соотв.
    `O_1K=O_1M=3, O_2K=O_2N=5`.
    Проведем прямые `OM, ON.`
    Очевидно (радиусы внешней и внутренней окружностей перпендикулярны общей внешней касательной), что точки `O,O_1` и `M` лежат на одной прямой, как и точки `O,O_2,N`.
    Точка `K` лежит на прямой `MN`, по теореме Фалеса прямая `O_1K` параллельна `ON`, прямая `O_2K` параллельна `OM`.
    Тогда `OO_2=O_1K=3 => R=3+5=8`.
    Главная идея заключатеся в том, чтобы доказать, что `O_1KO_2O` параллелограмм. Это можно сделать разными способами.

    Ответ: `8`.
  • Вариант 1. Задача №4.
    Решите в натуральных числах уравнение `3^x+5^y+14=z!` (символ `z!` означает факториал `z`).

    Решение:
    `3^x+5^y=z!-14`.
    Пусть `z>=4 => z!-14` дает остаток `2` при делении на `4` и дает остаток `1` при делении на `3`.
    Остатки при делении на `4`:
    `5^y=(4+1)^y` дает остаток `1`, `3^x=(4-1)^x` дает остаток `(-1)^x`, поэтому `x` должен быть четным.
    Остатки при делении на `3`:
    `z!-14-3^x` дает остаток `1` при делении на 3, поэтому `5^y=(6-1)^y` дает остаток `(-1)^y`, следовательно `y` должен быть четным.
    `x=2k, y=2n => 3^x+5^y=9^k+25^n`.
    Пусть `z>=7 => z!-14` делится на `7`, значит `9^k+25^n` делится на `7`.
    `9^k+25^n=(7+2)^k+(21+4)^n` дает остаток `2^k+4^n` при делении на `7`.
    `2^k+4^n=2^k+2^(2n)=2^a(2^b+1)`, где `a=k` или `2n`.
    `2^b+1` (где `b>=0`) должен делится на `7`, значит `2^b` дает остаток `6` при делении на `7`.
    `2^3=8` дает остаток `1 => 2^(3m)` дает остаток `1`, `2^(3m+1)` дает остаток `2`, `2^(3m+2)` дает остаток `4`. Противоречие.
    Получили, что нет решений при `z>=7`.
    `z=6 => 9^k+25^n=706 => n<=2`:
    `n=1` - решений нет.
    `n=2 => k=2 => (x,y)=(4,4)`.
    `z=5 => 9^k+25^n=106 => n=1 => k=2 => (x,y)=(4,2)`.
    `z=4 => 9^k+25^n=10` - решений нет.
    `z<=3 => 3^x+5^y=6-14=-8` - решений нет.

    Ответ: `(x,y,z)=(4,2,5), (4,4,6)`.
  • Вариант 1. Задача №5.
    В стране Альфия `150` городов, некоторые из  которых соединены железно-дорожными экспрессами, не останавливающимися на промежуточных станциях.  Известно, что любые четыре города можно разбить на две пары так, что между городами каждой пары курсирует экспресс.  Какое наименьшее число пар городов  соединены экспрессами?

    Решение:
    Решим задачу для `n>=4` городов, которые обозначим, как `1,2,...,n`.
    `a=b` означает, что города соединены между собой экспрессом, `a!=b` означает, что нет экспресса между городами.
    Различных соотношений вида `a!=b` может быть не больше `n`. Предположим обратное, пусть таких соотношений `n+1` или больше.
    В каждом соотношении участвует два города, всего таких городов `2n+2` или больше.
    Разных городов по условию `n`, поэтому какой-то город встречается минимум в трех разных соотношениях (принцип Дирихле).
    Т.е. `a!=b, a!=c, a!=d`, для некоторых различных городов `a,b,c,d`.
    Тогда четверка `(a,b,c,d)` противоречит условию задачи.

    Общее кол-во пар городов равно `C_n^2`, чтобы выполнилось условие задачи, не менее `C_n^2-n` пар городов должны быть соединены экспрессами.
    Построим пример для `C_n^2-n`:
    `1!=2, 2!=3, 3!=4,...,n-1!=n, n!=1`.
    Возьмем произвольную четверку `(a,b,c,d)`. Разбиения по парам: `(ab,cd), (ac,bd), (ad,bc)`. Пусть в каждом паре есть звено `x!=y`.
    Если во всех трех плохих звеньях есть одна буква, это противоречит построенному примеру (где каждый город не соединен экспрессом ровно с двумя другими городами).
    Легко заметить, что получаем три звена вида `x!=y, y!=z, z!=x`. Это опять противоречит примеру, поскольку `n>=4` и в примере "замыкание" возможно только при `n`.

    Ответ: `C_150^2-150`.
  • Вариант 1. Задача №6.
    В конус с радиусом основания `2` и образующей `4` помещены три шара радиуса `r`. Они касаются друг друга (внешним образом), боковой поверхности конуса, и первые два шара касаются основания конуса. Найдите максимальное значение `r`.

    Решение:
    Проведем секущую через центр трех шаров.
    Секущая конуса будет треугольником с основанием `4` (два радиуса) и боковыми сторонами `4`, следовательно треугольник правильный.
    Известно, что два шара касаются основания и друг друга.
    Рассмотрим треугольник `AHC`, по теореме Пифагора найдем высоту, она равна `2*sqrt(3)`.
    Радиус вписанного в него шара считается по формуле `S/p`, где `p` - полупериметр.
    Площадь треугольника равна `2*sqrt(3)`, полупериметр `3 + sqrt(3)`.
    Упростив `(2sqrt(3))/(3 + sqrt(3))` получим, что радиус вписанной окружности равен `sqrt(3) - 1`.
    Остальные шары будут вписываться аналогичным образом, так как треугольник равносторонний.
    image
    - рисунок к задаче.
  • Вариант 2. Задача №1.
    В турнире по армреслингу участвуют `2^n+6` спортсменов, где `n` - натуральное число, большее `7`. За победу даётся `1` очко, за поражение - `0` очков. Перед каждым туром пары по жребию составляют из участников, имеющих равное количество очков (те, кому не нашлось пары, пропускают тур). Сколько участников после окончания `7` тура наберут по `4` очка?

    Решение:
    `f_m(k)` - кол-во спортсменов, которые наберут `k` очков после `m`-го тура.
    Например, `f_1(1)=f_1(0)=2^(n-1)+3, f_0(0)=2^n+6`.
    Легко заметить следующие рекуррентные соотношения:
    `f_(m+1)(k+1)=1/2f_m(k)+1/2f_m(k+1)`, если `f_m(k), f_m(k+1)` четны.
    `f_(m+1)(k+1)=1/2(f_m(k)-1)+1/2f_m(k+1)`, если `f_m(k)` нечетен, `f_m(k+1)` четен.
    `f_(m+1)(k+1)=1/2f_m(k)+1/2(f_m(k+1)-1)+1`, если наоборот.
    `f_(m+1)(k+1)=1/2(f_m(k)-1)+1/2(f_m(k+1)-1)+1=1/2f_m(k)+1/2f_m(k+1)`, если оба нечетны.
    `f_2(2)=2^(n-2)+1, f_3(3)=2^(n-3), f_m(m)=2^(n-m)` при всех `m>=4`.
    `f_2(0)=2^(n-2)+2, f_3(0)=2^(n-3)+1, f_m(0)=2^(n-m)+1` при всех `m>=4`.
    `f_2(2)=2^(n-2)+1, f_2(1)=2^(n-1)+3, f_2(0)=2^(n-2)+2`,
    `f_3(3)=2^(n-3), f_3(2)=2^(n-2)+2^(n-3)+2, f_3(1)=2^(n-2)+2^(n-3)+3`,
    `f_3(0)=2^(n-3)+1`,
    `f_4(4)=2^(n-4), f_4(3)=2^(n-2)+1, f_4(2)=2^(n-2)+2^(n-3)+2`,
    `f_4(1)=2^(n-2)+2, f_4(0)=2^(n-4)+1`,
    `f_5(5)=2^(n-5), f_5(4)=2^(n-5)+2^(n-3), f_5(3)=2^(n-2)+2^(n-4)+2`,
    `f_5(2)=2^(n-2)+2^(n-4)+2, f_5(1)=2^(n-3)+2^(n-5)+1, f_5(0)=2^(n-5)+1`,
    `f_6(4)=2^(n-6)+2^(n-5)+2^(n-4)+2^(n-3)+1, f_6(3)=2^(n-4)+2^(n-2)+2`,
    `f_7(4)=2^(n-7)+2^(n-6)+2^(n-2)+2`.

    Ответ: `2^(n-7)+2^(n-6)+2^(n-2)+2`.
  • Вариант 2. Задача №2.
    Найдите наименьшее значение выражения при `a,b>0`
    `(|4a-10b|+|2(a-bsqrt3)-5(asqrt3+b)|)/sqrt(a^2+b^2)`.

    Решение:
    Наше выражение обозначим через `F(a,b)`.
    Пусть `a^2+b^2=c^2 => (a/c)^2+(b/c)^2=1`.
    `F(a,b)=A/B=(A/c)/(B/c)=F(a/c, b/c)`.
    `F` не зависит от `c`, поэтому можем сказать, что `c=1`.
    Тогда существует такой `x in (0;pi/2)`, что `a=sinx, b=cosx`. Учли то, что `a,b>0`.
    `F(x)=|4sinx-10cosx|+|(5sqrt3-2)sinx+(2sqrt3+5)cosx|`.
    Заметим, что `4^2+10^2=116=(5sqrt3-2)^2+(2sqrt3+5)^2`.
    `1/sqrt116*F(x)=|sin(x-alpha)|+|sin(x+beta)|`, где `cosalpha=4/sqrt116, cosbeta=(5sqrt3-2)/sqrt116`.
    `0<4/sqrt116< 1/2<(5sqrt3-2)/sqrt116 => 0< beta< pi/3< alpha< pi/2`.
    `x+beta in (0;pi/2+pi/3) => |sin(x+beta)|=sin(x+beta)`.
    Пусть `x>=alpha => 1/sqrt116*F(x)=sin(x-alpha)+sin(x+beta)=`
    `=2sin(x-1/2alpha+1/2beta)*cos(1/2alpha+1/2beta)`.
    Второй сомножитель константа, `x-1/2alpha+1/2beta in (0;pi/2)`, поэтому минимум будет при минимальном `x=alpha`.
    `F_min=sqrt116*2sin(1/2alpha+1/2beta)*cos(1/2alpha+1/2beta)=sqrt116*sin(alpha+beta)`.
    `sin(alpha+beta)=10/sqrt116*(5sqrt3-2)/sqrt116+(2sqrt3+5)/sqrt116*4/sqrt116`.
    `F_min=1/sqrt116*(-20+50sqrt3+8sqrt3+20)=(58sqrt3)/sqrt116=sqrt87`.
    Пусть `x<=alpha => 1/sqrt116*F(x)=`
    `=2cos(x-1/2alpha+1/2beta)*sin(1/2alpha+1/2beta)`.
    Далее все аналогично, получаем, что `F_min=F(alpha)=sqrt87`.

    Ответ: `sqrt87`.
  • Вариант 2. Задача №3.
    Внутри окружности `omega` расположена касающаяся её в точке `K` окружность `omega_1`, окружность `omega_2` касается окружности `omega_1` в точке `L` и пересекается с окружностью `omega` в точках `M` и `N`. Оказалось, что точки `K,M,N` лежат на одной прямой. Найдите радиус окружности `omega`, если радиусы окружностей `omega_1` и `omega_2` равны `4` и `7` соответственно.

    Решение:
    См. решение задачи №3 из варианта 1. Задачи практически идентичны.
  • Вариант 2. Задача №4.
    Решите в натуральных числах уравнение:
    `2^x+5^y+63=z!` (символ `z!` означает факториал `z`).

    Решение:
    `z>=5=> z!` делится на `4`, `z!-5^y-63` дает остаток `2` при делении на `5`.
    `2^4=16 => 2^(4k)` дает остаток `1`, `2^(4k+1)` дает остаток `2`, `2^(4k+2)` дает остаток `4`, `2^(4k+3)` дает остаток `3`.
    `x=4k+1`.
    `z!-63` делится на `3 => 2^x+5^y` делится на `3`.
    `2^x+5^y=(3-1)^x+(6-1)^y` дает остаток `(-1)^x+(-1)^y` при делении на `3`.
    Следовательно, `x,y` разной четности `=> y=2n`.

    `z>=7 => 2^x+5^y` делится на `7`.
    `2^x+5^y=2^(4k+1)+5^(2n)=2*16^k+25^n` дает остаток `2*2^k+4^n` при делении на `7`.
    `2^(k+1)+2^(2n)=2^a(2^b+1)`, где `a=k+1` или `2n`.
    `2^b+1` (где `b>=0`) должен делится на `7`, значит `2^b` дает остаток `6` при делении на `7`.
    `2^3=8` дает остаток `1 => 2^(3m)` дает остаток `1`, `2^(3m+1)` дает остаток `2`, `2^(3m+2)` дает остаток `4`. Противоречие.
    Получили, что нет решений при `z>=7`.
    `z=6 => 2*16^k+25^n=657 => k=1, n=2 => x=5, y=4`.
    `z=5 => 2*16^k+25^n=57 => k=1, n=1 => x=5, y=2`.
    `z<=4` - решений нет.

    Ответ: `(x,y,z)=(5,4,6), (5,2,5)`.

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