Автор: Лыков А., к.ф.-м.н., академический руководитель Школы Высшей Математики и ШАДХелпера.
Гробом принято называть задачу на экзамене или олимпиаде, которую почти невозможно решить. В статье мы приведём несколько примеров из вступительных экзаменов в ШАД и классифицируем гробы на три типа.
В контексте экзаменов в ШАД, гробы появляются на экзаменах не каждый год и, как правило, находятся среди последних задач письменного экзамена. Выделим следующие типы гробов.
I) ''Классический'' — решение у задачи существует, полностью опирается на программу, использует необычные приёмы в решении, сложная даже для специалистов. Рассмотрим примеры.
При каких натуральных
существует квадратная матрица порядка
с элементами
такая, что ее квадрат — это матрица из одних единиц?
Решение
Значение
, очевидно, подходит. Далее
. Пусть
— матрица размера
из 0 и 1, для которой
— матрица из одних единиц. Известно, что
и что если
— собственное значение матрицы
геометрической кратности
, то
— собственное значение матрицы
геометрической кратности
. Так как
— матрица ранга 1, то
— её собственное значение геометрической и алгебраической кратности
и
— собственное значение кратности 1. Значит, с учётом также того, что
, получаем, что
. В частности,
- полный квадрат.
Пусть
. Для перестановки
обозначим через
матрицу, в которой
, а остальные элементы равны 0.
Ясно, что. Пусть
. Рассмотрим блочную матрицу
, состоящую из
блоков размера
, в которой каждая блочная строка есть
-матрица
Например, при
это
Тогда
-блок матрицы
есть
Верно ли, что почти все (все, кроме конечного числа) натуральные числа представимы в виде
, где
— количество делителей числа
?
Решение
Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое. Видео-разбор занимает более 30 минут.
II) "Технарь" — решение опирается на программу, но использует технику и идеи из других математических теорий (например, из теории марковских цепей), о которых не было заявлено в программе. Для решения таких задач полезно знать много "разной математики" вне программы.
За столом сидят
старателей, перед каждым из которых находится кучка золотого песка. Каждую минуту происходит следующее: по общей команде каждый из них перекладывает в свою кучку половину песка из кучки левого соседа и половину — из кучки правого соседа. Опишите асимптотическое поведение кучек (а) при
; (б) при произвольном
.
Решение
Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое.
Решение этой задачи (и не только её) опирается на приёмы, часто применяемые в теории марковских цепей.
Какой минимальной длины существует цепочка из цифр, такая, что в ней в качестве фрагментов четырёх из подряд идущих цифр присутствует все не начинающиеся с нуля цепочки из
цифр?
Решение
Рассмотрим ориентированный граф с вершинами — трёхзначными числами (которые могут начинаться с нуля) и рёбрами вида
(= четырёхзначное число
).
Из каждой вершины выходит 10 рёбер и в каждую входит 10 рёбер, поэтому в графе есть эйлеров цикл. Запишем по кругу число изцифр, соответствующее этому циклу. Разрежем его и выпишем в строку так, чтобы фрагмент
стоял в конце. Сотрём последний нуль и получим
-значное число, в котором встречаются по разу все 4-значные числа (которые могут начинаться с нуля), кроме
.
Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными. Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными.
Пусть теперь дано кратчайшее-значное число
, в котором встречаются все 9000 4-значных чисел, не начинающихся с нуля (хотя бы раз). Тогда
число нулей в A: при сдвиге на одну цифру вправо в
мы получим, возможно, новое число, если только эта цифра не нуль. Рассмотрим множества чисел
Оценим снизу число нулей в
.
Все тройные нули из чисел вне пересекаются и содержатся в
— уже
нулей.
Пары нулей изне пересекаются и максимум 9 из этих 90 пар могли ,,утонуть`` в тройках нулей из
. Итого,
новых нулей. Наконец максимум
из
одинарных нулей из
уже могли быть учтены в
и
, итого
новых нулей. Итого, число
содержит как минимум
Знание теории последовательностей де Брейна сильно поможет при решении этой задачи.
III) "Умник" — решение опирается на факты и объекты не из официальной программы.
Пусть
— ограниченная гладкая функция, причём её среднее значение на любой окружности радиуса
равно значению в центре этой окружности. Докажите, что
постоянна.
Решение
Решение можно найти в задачнике ШАД Хелпера. Здесь мы не приводим решение, так как оно достаточно громоздкое и весьма техническое.
Известные нам решения этой задачи опираются либо на теорию обобщенных функций, либо на теорию мартингалов. Пишите свои решения в комментариях. Ни того, ни другого в официальной программе нет.
Формулировка сразу наталкивает на мысль о гармонических функциях (в смысле теории марковских процессов).
Условие. Известно, что случайный вектор
распределён нормально:
Найдите измеримую функцию
минимизирующую математическое ожидание
Решение
Преобразуем выражение:
По свойству условного математического ожидания минимум последнего выражения достигается при
Последнее равенство не совсем корректно. Более формально нужно написать
приДалее вычислим
. Представим случайную величину
в следующем виде:
где
гауссовская случайная величина независимая от
,
некоторая константа, которую мы сейчас найдем. Имеем равенство
Откуда находим
Найдём параметры
:
Далее,
. Поэтому получаем
Следовательно,
Условного математического ожидания в программе нет. Решения не опирающегося на УМО мы, к сожалению, не знаем. Пишите в комментариях свои решения.
Наличие сложных задач поднимает интерес к испытаниям у сильных студентов, создаёт дополнительных дух соперничества. Это однозначно хорошо. Однако мы считаем, что наличие гробов типа "Умник" и "Технарь" не совсем честно и справедливо. Возможно стоит снабжать официальную программу фразой "Дополнительным преимуществом для поступающих может быть знание марковских цепей, теории графов, комплексного анализа и т.д..".
Всем успехов в изучении математики и желаем удачи на экзаменах!
*Условия задач и решений взяты с сайта школы ШАДХелпер. Если у кого-то будет желание прочитать решения задач из статьи, пишите на сайт школы и Вам откроют доступ к соответствующим задачам.