Как стать автором
Обновить

Гробы на экзаменах в ШАД

Время на прочтение4 мин
Количество просмотров4.6K

Автор: Лыков А., к.ф.-м.н., академический руководитель Школы Высшей Математики и ШАДХелпера.

Гробом принято называть задачу на экзамене или олимпиаде, которую почти невозможно решить. В статье мы приведём несколько примеров из вступительных экзаменов в ШАД и классифицируем гробы на три типа.

В контексте экзаменов в ШАД, гробы появляются на экзаменах не каждый год и, как правило, находятся среди последних задач письменного экзамена. Выделим следующие типы гробов.

I) ''Классический'' — решение у задачи существует, полностью опирается на программу, использует необычные приёмы в решении, сложная даже для специалистов. Рассмотрим примеры.

  1. При каких натуральных N существует квадратная матрица порядка N с элементами 0,1 такая, что ее квадрат — это матрица из одних единиц?

    Решение

    Значение N=1, очевидно, подходит. Далее N>1. Пусть A — матрица размера N\times N из 0 и 1, для которой A^2=({\bf 1}) — матрица из одних единиц. Известно, что Sp(A^2)=(Sp A)^2 и что если \lambda — собственное значение матрицы A геометрической кратности s, то \lambda^2 — собственное значение матрицы A^2 геометрической кратности \geq s. Так как A^2=({\bf 1}) — матрица ранга 1, то 0 — её собственное значение геометрической и алгебраической кратности N-1 и tr A=N — собственное значение кратности 1. Значит, с учётом также того, что tr A\geq 0, получаем, что Sp(A)=\{\sqrt{N},0,\ldots,0\}. В частности, N=n^2 - полный квадрат.

    Пусть N=n^2. Для перестановки \sigma\in S_n обозначим через M_\sigma матрицу, в которой m_{ij}=1\iff \sigma(i)=j, а остальные элементы равны 0.
    Ясно, что M_\sigma M_\tau=M_{\sigma \tau}. Пусть \rho=(12\ldots n). Рассмотрим блочную матрицу A, состоящую из n^2 блоков размера n\times n, в которой каждая блочная строка есть (n\times n^2)-матрица

    (E\,M_\rho \, M_{\rho^2}\,\ldots M_{\rho^{n-1}}).

    Например, при n=3 это

    \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}.

    Тогда (ij) -блок матрицы A^2 есть

    \sum_{k=0}^{n-1} M_{\rho^k}M_{\rho^{j-1}}=\sum_{k=0}^{n-1} M_{\rho^k}=({\bf 1}).

    Ссылка на задачу

  2. Верно ли, что почти все (все, кроме конечного числа) натуральные числа представимы в виде {n + \tau(n)}, где \tau(n) — количество делителей числа n?

    Решение

    Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое. Видео-разбор занимает более 30 минут.

II) "Технарь" — решение опирается на программу, но использует технику и идеи из других математических теорий (например, из теории марковских цепей), о которых не было заявлено в программе. Для решения таких задач полезно знать много "разной математики" вне программы.

  1. За столом сидят n старателей, перед каждым из которых находится кучка золотого песка. Каждую минуту происходит следующее: по общей команде каждый из них перекладывает в свою кучку половину песка из кучки левого соседа и половину — из кучки правого соседа. Опишите асимптотическое поведение кучек (а) при n=3; (б) при произвольном n.

    Решение

    Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое.

    Решение этой задачи (и не только её) опирается на приёмы, часто применяемые в теории марковских цепей.

  2. Какой минимальной длины существует цепочка из цифр, такая, что в ней в качестве фрагментов четырёх из подряд идущих цифр присутствует все не начинающиеся с нуля цепочки из 4 цифр?

    Решение

    Рассмотрим ориентированный граф с вершинами — трёхзначными числами (которые могут начинаться с нуля) и рёбрами вида (abc,bcd) (= четырёхзначное число abcd).
    Из каждой вершины выходит 10 рёбер и в каждую входит 10 рёбер, поэтому в графе есть эйлеров цикл. Запишем по кругу число из 10000 цифр, соответствующее этому циклу. Разрежем его и выпишем в строку так, чтобы фрагмент 0000 стоял в конце. Сотрём последний нуль и получим 9999-значное число, в котором встречаются по разу все 4-значные числа (которые могут начинаться с нуля), кроме 0000.

    Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными. Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными.
    Пусть теперь дано кратчайшее n-значное число X=a_1a_2\ldots a_n, в котором встречаются все 9000 4-значных чисел, не начинающихся с нуля (хотя бы раз). Тогда n\geq 9000+число нулей в A: при сдвиге на одну цифру вправо в X мы получим, возможно, новое число, если только эта цифра не нуль. Рассмотрим множества чисел

    A=\{c000\mid c\ne 0\},\;B=\{bc00\mid a\ne 0\},\;C=\{abc0\mid a\ne 0\}, \;\;|A|=9,\,|B|=90,\;|C|=900.

    Оценим снизу число нулей в X.
    Все тройные нули из чисел в A не пересекаются и содержатся в X — уже 3\cdot 9 нулей.
    Пары нулей из B не пересекаются и максимум 9 из этих 90 пар могли ,,утонуть`` в тройках нулей из A. Итого, \geq 2\cdot (90-9) новых нулей. Наконец максимум 90 из 900 одинарных нулей из C уже могли быть учтены в A и B, итого \geq 900-90 новых нулей. Итого, число X содержит как минимум

    3\cdot 9+2\cdot(90-9)+900-90=999 \text{ нулей.}

    Ссылка на задачу

Знание теории последовательностей де Брейна сильно поможет при решении этой задачи.

III) "Умник" — решение опирается на факты и объекты не из официальной программы.

  1. Пусть f:\mathbb{R}^2 \rightarrow \mathbb{R} — ограниченная гладкая функция, причём её среднее значение на любой окружности радиуса 1 равно значению в центре этой окружности. Докажите, что f постоянна.

    Решение

    Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое и весьма техническое.

    Известные нам решения этой задачи опираются либо на теорию обобщенных функций, либо на теорию мартингалов. Пишите свои решения в комментариях. Ни того, ни другого в официальной программе нет.

    Формулировка сразу наталкивает на мысль о гармонических функциях (в смысле теории марковских процессов).

  2. Условие. Известно, что случайный вектор (X, Y) распределён нормально:

    (X,Y)\sim N(\begin{pmatrix} 1\\2 \end{pmatrix}, \begin{pmatrix} 1&1\\1&2 \end{pmatrix})

    Найдите измеримую функцию g(x) минимизирующую математическое ожидание

    E( −24Y^4 + (g(X))^2 + 2g(X)Y^2 + 4)
    Решение

    Преобразуем выражение:

    E( -24Y^4 + (g(X))^2 + 2g(X)Y^2 + 4) = E((g(X) + Y^2)^2 - 25Y^4 + 4) = E((g(X) + Y^2)^2 - 25EY^4 + 4.

    По свойству условного математического ожидания минимум последнего выражения достигается при g(X) = -E(Y^2|X).
    Последнее равенство не совсем корректно. Более формально нужно написать

    g(x) = -E(Y^2|X=x)
    при x\in \mathbb{R}.

    Далее вычислим E(Y^2|X). Представим случайную величину Y в следующем виде:

    Y = \alpha X + Z,

    где Z гауссовская случайная величина независимая от X, \alpha некоторая константа, которую мы сейчас найдем. Имеем равенство

    \mathrm{cov}(Y,X) = \alpha \mathrm{cov}(X,X) = \alpha DX

    Откуда находим

    \alpha = \frac{\mathrm{cov}(Y,X)}{DX} = 1

    Найдём параметры Z:

    EZ = EY - \alpha EX = 2- 1 = 1
    DZ = DY- \alpha^2 DX  = 2 - 1 = 1.

    Далее, EZ^2 = DZ + (EZ)^2 = 2. Поэтому получаем

    E(Y^2|X) = E( X^2 + 2 X Z + Z^2|X) = X^2 + 2X EZ + EZ^2 = X^2+2X+ 2.

    Следовательно,

    g(X) = -( X^2+2X+ 2)

    Ссылка на задачу

    Условного математического ожидания в программе нет. Решения не опирающегося на УМО мы, к сожалению, не знаем. Пишите в комментариях свои решения.

Наличие сложных задач поднимает интерес к испытаниям у сильных студентов, создаёт дополнительных дух соперничества. Это однозначно хорошо. Однако мы считаем, что наличие гробов типа "Умник" и "Технарь" не совсем честно и справедливо. Возможно стоит снабжать официальную программу фразой "Дополнительным преимуществом для поступающих может быть знание марковских цепей, теории графов, комплексного анализа и т.д..".

Всем успехов в изучении математики и желаем удачи на экзаменах!

*Условия задач и решений взяты с сайта школы ШАДХелпер. Если у кого-то будет желание прочитать решения задач из статьи, пишите на сайт школы и Вам откроют доступ к соответствующим задачам.

Теги:
Хабы:
-12
Комментарии3
2

Публикации

Истории

Ближайшие события