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

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

Олимпиада «Физтех 2014» / Олимпиада МФТИ по математике 2013-2014 / Задания и решения
  • Задача №11 - отборочный этап по математике (олимпиада Физтех 2014)
    Монотонные числа

    Найдите количество десятизначных чисел, в десятичной записи которых могут встречаться только цифры `1, 2, 3, 4` и таких, что каждая цифра не меньше предыдущей.

    Решение:
    Не совсем ясно, убывают цифры или возрастают, но разницы нет, т.к. и так и так получится одно и тоже количество. Зеркальные случаи.
    Далее решение без комбинаторных изысков:
    `a_k, b_k, c_k, d_k` - количество чисел удовлетворяющих условию задачи, с первыми цифрами `1,2,3,4` соответственно и `k` знаками.
    Тогда `a_1=b_1=c_1=d_1=1`.
    Также, можно заметить, что `a_(k+1)=a_k+b_k+c_k+d_k`
    `b_(k+1)=b_k+c_k+d_k`
    `c_(k+1)=c_k+d_k`
    `d_(k+1)=d_k`
    Отсюда получим
    `a_10=a_1+9b_1+45c_1+165d_1=220`
    `b_10=b_1+9c_1+45d_1=55`
    `c_10=c_1+9d_1=10`
    `d_10=d_1=1`
    Значит, наше искомое число равно `220+55+10+1=286`.

    Ответ: `286`.
  • Задача №12 - отборочный этап по математике (олимпиада Физтех 2014)
    Шесть лучей

    На сторонах `AB` и `AD` квадрата `ABCD` со стороной `16` отмечены точки `E` и `F` соответственно. Угол `ECF` равен `60^0`. Из вершин `B` и `D` проведены перпендикуляры к отрезкам `CE` и `CF`. Какая наибольшая площадь может быть у четырехугольника с вершинами в основаниях этих перпендикуляров?

  • Задача №13
    Параллелепипед

    Площадь проекции прямой четырехугольной призмы `ABCDA_1B_1C_1D_1` с ромбом `ABCD` в основании на плоскость, перпендикулярную его диагонали `AC_1`, равна `sqrt89`. Чему будет равна площадь проекции параллелепипеда на плоскость, перпендикулярную диагонали `BD_1`, если `A A_1=8, AC=6, BD=5`?

  • Задача №14
    Непрямоугольные треугольники

    На клетчатой бумаге по линиям сетки выделили прямоугольник `10×15` клеток. В нем отметили все узлы, в том числе и лежащие на его границе. Какое наибольшее число отмеченных узлов можно выбрать так, чтобы никакие три из них не являлись вершинами прямоугольного треугольника?

    Решение:
    Возьмем узлы на границе первых столбца и строки. Исключим угловой узел, остается `10+15=25` узлов. Из-за исключения углового узла, из любых трех узлов минимум две попадут на одну сторону таблицы, поэтому любые три узла образуют тупоугольный треугольник.
    Предположим, что отметили `26` или больше узлов. Возьмем произвольный отмеченный узел, который лежит на пересечении двух линий сетки (горизонтальной и вертикальной). Чтобы не получился прямоугольный треугольник, как минимум на одной из двух линий нет другого отмеченного узла. Эта линия называется "бедной". Для каждого отмеченного узла есть минимум одна своя бедная линия, значит всего бедных линий минимум `26`. Всего линий `11+16=27`, значит не бедных линий максимум `1`.
    Теперь попробуем разместить `26` точек по `11` линиям. Получаем минимум `2` не бедные линии - противоречие.

    Ответ: `25`.
  • Задача №15
    Лучи на координатной плоскости

    Из начала координат проведено `720` лучей, которые делят координатную плоскость на углы в `0,5^0`. Известно, что четыре из них совпадают с координатными полуосями. Найдите сумму абсцисс точек пересечения этих лучей с прямой `y=10–x`.

    Решение:
    1. Для начала рассмотрим `4` луча, которые совпадают с полуосями. Очевидно, что прямая `y=10-x` пересчет два из них (положительные полуоси), при этом сумма абсцисс точек пересечения равна `10`.
    2. Теперь рассмотрим первую четверть. Кроме границ-полуосей, в этой четверти `179` лучей. Важно не ошибиться с подсчетом лучей!
    Каждый луч вида `y=kx`, где `k=tanalpha, alpha in (0;90^0)` - угол, который составляет прямая с осью `X`.
    Разобьем на пары по углам, т.е. `(89,5^0;0,5^0), (89^0;1^0), ..., (45,5^0;44,5^0)` - всего `89` пар вида `(alpha;pi/2-alpha)` и остается еще `1` угол `45^0`.
    Посчитаем для каждой пары сумму абсцисс точек пересечения соотв. пары лучей с прямой `y=10-x`.
    `kx=10-x => x=10/(k+1)=10/(tanalpha+1)`.
    Тогда сумма равна `10/(tanalpha+1)+10/(tan(pi/2-alpha)+1)=10/(tanalpha+1)+10/(cottanalpha+1)=10`.
    Еще луч `y=x`, ее абсцисса пересечения равна `5`.
    Общая сумма `89*10+5=895`.
    3. Теперь можно посчитать сумма абсцисс для лучей, которые лежат во `2` и `4` четвертях. Понятно, что все лучи лежащие на прямой `y=-x` или ниже нее - не пересекутся с `y=10-x`.
    Остальные лучи можно разбить по парам (один луч берем из `2` четверти, другой симметричный относительной прямой `y=x` из `4` четверти). Всего таких лучей будет `178`, а пар `89`.
    Каждая такая пара даст сумму абсцисс, равной `10`. Можно это получить исходя из геометрических соображений, или аналогично пункту `2`.
    Общая сумма равна `890`.

    Итоговая сумма абсцисс `10+895+890=1795`.

    Ответ: `1795`.
  • Задача №16
    Кузнечик

    Кузнечик прыгает по вершинам правильного треугольника `ABC`, прыгая каждый раз в одну из соседних вершин. Сколькими способами он может попасть из вершины `A` обратно в вершину `A` за `12` прыжков?

    Решение:
    Пусть кузнечик может совершить `1` прыжок, тогда число способов вернуться в вершину `A` равно `0`, число способов попасть на вершину `B` равно `1`.
    Пусть всего `2` прыжка. Тогда число способов попасть обратно равно `2`, а число способов попасть на вершину `B` равно `1`.
    Пусть `A(k)` - число способов вернуться в вершину `A` за `k` прыжков, `B(k)` - число способов попасть на вершину `B` за `k` прыжков. Тогда получаем, что `A(k+1)=B(k)+C(k)=2B(k)`.
    Также `B(k+1)=A(k)+C(k)=A(k)+B(k)`
    (`C(k)` аналогичный показатель для вершины `C`, очевидно, что `C(k)=B(k))`
    Итак, имеем два рекуррентных соотношения: `A(k+1)=2B(k), B(k+1)=A(k)+B(k)`
    `A(1)=0, B(1)=1, A(2)=2, B(2)=1, A(3)=2, B(3)=3` и т.д. Получаем `A(12)=1366`.

    Ответ: `1366`.
  • Задача №17
    Цилиндр
    В основании четырехугольной пирамиды `SABCD` лежит квадрат `ABCD` со стороной `AB=12`. На продолжении диагонали `CA` за точку `A` выбрана точка `H` так, что `AH=3CA`. Отрезок `SH=6` перпендикулярен плоскости основания пирамиды. Какой наибольший объем `V` может иметь цилиндр, расположенный внутри пирамиды так, что одно из его оснований лежит на основании пирамиды? В ответе укажите величину `V/pi`.

  • Задача №18
    Игла
    Прямоугольный параллелепипед `30×35×42`, разбитый на `44100` единичных кубиков, проткнули иглой по его диагонали. Сколько единичных кубиков протыкает игла?

    Решение:
    Верна следующая формула:
    `D` (число проткнутых кубиков) `=30+35+42-НОД(30,35)-НОД(30,42)-НОД(35,42)+НОД(30,35,42)`.
    `30=2*3*5, 35=5*7, 42=2*3*7`
    Тогда `D=30+35+42-5-6-7+1=90`.
    Полное решение выложу потом.

    Ответ: `90`.
  • Задача №19
    Игра на выбывание
    В турнире участвовали `89` теннисистов. Все игры проходили на одном корте. Спортсмен, проигравший хотя бы одну игру, выбывает из турнира. Известно, что у участников каждой встречи количество предыдущих побед отличалось не более чем на одну. Какое наибольшее число игр мог сыграть победитель турнира?

    Решение:
    Красивая задача на принцип Дирихле `+` индукцию `+` числа Фибоначчи.
    `f(k)` - максимальное количество игр, которые сыграл победитель турнира с `k` участниками.
    Тогда `f(2)=1, f(3)=2, f(4)=2` - победитель не может выиграть последовательно у остальных троих, т.к. нарушается условие задачи (количество предыдущих побед отличалось не более чем на одну).
    `f(5)=3`. Аналогично `f(5)<4`, а `f(5)=3`, когда теннисисты разбиваются на две группы по `2` и `3` человека.

    Пусть `k=6,7 => f(k)=3`, т.к. Победитель и Финалист выиграли в своих группах, поэтому если `f(k)=4`, значит Финалист провел минимум `2` игры `=>` в его группе минимум `3` человека, значит в группе Победителя максимум 4 человека, но тогда до Финала тот провел `2` игры, противоречие.
    `f(8)=4`, т.к. тогда можно разбить на две группы по `5` и `3` человека, при этом `f(5)=3, f(3)=2, |3-2|<=1`.

    Аналогично, если `k=9,10,11,12`, то `f(k)=4`. Если `f(k)=5`, то Финалист провел в своей группе минимум `3` игры `=>` в этой группе минимум `5` человек `=>` в группе Победителя максимум `7` человек, что противоречит тому, что он провел `4` игры в своей группе.
    `f(13)=5`, разбиваем на две группы по `8` и `5` человек.
    Аналогичными рассуждениями получаем, что `f(k)=5` при `k=13,...,20`.
    `f(21)=6, f(k)=6` при `k=22,...,33`
    `f(34)=7, f(k)=7` при `k=35,...,54`
    `f(55)=8, f(k)=8` при `k=56,...,88`.
    `f(89)=9`.

    Ответ: `9`.
  • Задача №20
    Режем многоугольник
    В выпуклом `18`-угольнике проводят все его диагонали. На какое наибольшее число частей могут его разбить?

    Решение:
    Рассмотрим общую задачу, т.е. число вершин многоугольника равно `n`.
    Очевидно, что максимальное число разбиений будет в том случае, если никакие три диагонали не пересекутся в одной точке. Для каждого `n>=3` такое число разбиений обозначим за `f(n)`.
    `f(3)=1, f(4)=4`.
    Выведем рекуррентную формулу для `f(n)`.
    Если к многоугольнику добавили одну вершину (стало `n+1` вершин), то из этой вершины можно провести `n-2` диагоналей (ко всем вершинам, кроме соседних и кроме самого себя).
    Число пересечений этих диагоналей со старыми равно `C_n^3` т.к. каждой точке пересечения соотв. `3` вершины, а всего вершин `n`. Каждая такая точка пересечения дает новую часть, а также дополнительно все эти точки дадут `n-2+1=n-1` новых частей.
    `f(n+1)=f(n)+n-1+C_n^3=f(n)+n-1+((n-1)(n-2)(n-3))/6=`
    `=f(n)+((n-1)(n^2-2n+6))/6`.
    Из полученной рекуррентной формулы можно вывести точную формулу для `f(n)`, методом неопределенных коэффициентов или складывая разности `f(n+1)-f(n)=(n^3-3n^2+8n-6)/6`.
    Получим, что `f(n)=((n-1)(n-2)(n^2-3n+12))/24`.
    Поэтому `f(18)=(17*16*282)/24=3196`.

    Ответ: `3196`.

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