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

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

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

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

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

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

Решение

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

Пусть . Для перестановки $\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)$ . Рассмотрим блочную матрицу , состоящую из блоков размера $n\times n$ , в которой каждая блочная строка есть $(n\times n^2)$ -матрица

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

Например, при это

$\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}.$

Тогда -блок матрицы есть

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

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

Решение

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

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

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

Решение

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

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

Решение

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

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

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

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

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

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

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

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

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

Решение

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

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

Формулировка сразу наталкивает на мысль о гармонических функциях (в смысле теории марковских процессов).
Условие. Известно, что случайный вектор распределён нормально:

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

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

Решение

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

По свойству условного математического ожидания минимум последнего выражения достигается при
Последнее равенство не совсем корректно. Более формально нужно написать

при $x\in \mathbb{R}.$

Далее вычислим . Представим случайную величину в следующем виде:

$Y = \alpha X + Z,$

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

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

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

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

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

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

Далее, . Поэтому получаем

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

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

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

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

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

*Условия задач и решений взяты с сайта школы ШАДХелпер.

ссылка на оригинал статьи https://habr.com/ru/articles/869224/

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

Комментарии

Добавить комментарий Отменить ответ