Пробный экзамен в ШАД

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

Каждый год на экзамене в ШАД происходит одна и та же история.

Сильные студенты, которые хорошо знают математику, не добирают баллы. И дело часто не в знаниях. Кто-то «умирает» на второй задаче, потратив на неё три часа. Кто-то не успевает даже открыть последние задачи. Кто-то начинает паниковать, когда что-то идёт не по плану. В итоге результат оказывается сильно ниже реального уровня.

Проблема: экзамен — это не только математика

Когда смотришь на письменный экзамен в ШАД, кажется, что всё просто:

нужно решить как можно больше задач.

Но на практике это пятичасовой марафон, где проверяется не только математика, но и:

способность держать концентрацию в течение 5 часов
умение быстро оценивать сложность задачи
навык не закапываться, если решение не идёт
переключение между задачами
контроль состояния (усталость, тревожность, внимание)

И вот здесь многие «сыпятся». Парадокс в том, что человек может быть хорошо подготовлен теоретически, но при этом провалить экзамен именно как процесс.

Инсайт: экзамен — это отдельный навык

Экзамен — это не просто проверка знаний. Это навык, который нужно тренировать отдельно. Хорошая аналогия — спорт. Можно отлично знать теорию бега, но без тренировок марафон не пробежать.

С экзаменами ровно так же:

нарешенность задач — это база
но без опыта «боевого режима» этого недостаточно

Что реально помогает

Самый эффективный способ подготовки — это симуляция реального экзамена. Не «порешать вечером задачки», а именно:

сесть на 5 часов
получить незнакомый вариант
работать в условиях ограниченного времени
потом разобрать ошибки

И желательно — несколько раз.

Почему это работает

После первой такой попытки обычно вскрывается много неожиданного:

кто-то тратит 70% времени на одну задачу
кто-то не умеет оценивать, что «эта задача сейчас не берётся»
кто-то сильно проседает по энергии уже через 2–3 часа

И это те вещи, которые невозможно увидеть в обычной подготовке. Зато после 2–3 таких «прогонов» происходит качественный скачок:

появляется стратегия
выравнивается тайм-менеджмент
снижается тревожность

Где взять такую практику

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

Мы в ШАД Хелпер как раз проводим серию таких пробных экзаменов:

по выходным
с задачами, сопоставимыми по сложности с реальным экзаменом
с проверкой работ
с последующим разбором

По сути, это возможность заранее прожить экзамен и понять, где вы находитесь сейчас.

Итог

Хорошая подготовка к ШАД — это не только «решить много задач». Это ещё и:

научиться управлять временем
выстроить стратегию
привыкнуть к формату экзамена

И лучше сделать это заранее, а не в день настоящего экзамена.
Ниже мы разберём один пробный экзамен с 2024 года.

Задача 1. Найдите все , при которых существует базис трёхмерного евклидова пространства, в котором длина произвольного вектора () вычисляется по формуле

$|{bf v}|=sqrt{(a+1)z(z-4x)-a(x^2+2y^2)}.$

Решение

Задача эквивалентна такой: при каких квадратичная форма под знаком квадратного корня положительно определена. Запишем матрицу этой квадратичной формы:

$begin{pmatrix} -a & 0 & -2(a+1) \ 0 & -2a & 0 \ -2(a+1) & 0 & a+1end{pmatrix}$

и применим критерий Сильвестра (положительная определённость равносильна положительности угловых миноров):

$left{begin{aligned} &-a>0 \ &2a^2>0 \ &-2a(-a(a+1)-4(a+1)^2)>0 end{aligned} right.;;Longleftrightarrow;; left{begin{aligned} &a<0 \ &(a+1)(5a+4)<0 end{aligned} right.;;Longleftrightarrow;; -1<a<-tfrac 45.$

Ответ: $-1<a<-tfrac 45$ .

Задача 2. Каждой матрице $Ain mathbb{M}_3(mathbb{R})$ сопоставим линейный оператор

$phi_Acolon mathbb{M}_3(mathbb{R})to mathbb{M}_3(mathbb{R}),quad phi_A(X)=AX-XA.$

а) Может ли образ оператора иметь размерность 4?

б) Найдите собственные значения оператора , если собственные значения матрицы суть .

Решение

а) Так как $dim Imphi_A+dim text{K}er phi_A=dim mathbb{M}_3(mathbb{R})=9$ , то $dim Imphi_A=4iff dim text{Ker} phi_A=5$ . Но $text{Ker} phi_A=text{Cent}(A)$ . Пример:

$A=e_{11} ;;Longrightarrow;; text{Cent} A=left{begin{pmatrix} a_{11} & 0 & 0 \ 0 & a_{22} & a_{23} \ 0 & a_{32} & a_{33}end{pmatrix}; middle|;a_{ij}in mathbb{R}right} ;;Longrightarrow;; dim text{Cent} A=5.$

б) Известный факт: для произвольных матриц $A,Bin mathbb{M}_3(mathbb{R})$ уравнение Сильвестра имеет ненулевое решение , если и только если матрицы и имеют общее собственное значение. Поэтому

$muin text{Sp}(phi_A) ;;Longleftrightarrow;; exists Xin mathbb{M}_3(mathbb{R})setminus 0; AX-XA=mu X (iff AX=X(A+mu E)) ;;Longleftrightarrow;;$ $;;Longleftrightarrow;; text{Sp}(A)cap text{Sp}(A+mu E)ne varnothing ;;Longleftrightarrow;; exists lambda_i,lambda_jin text{Sp}(A);lambda_i=lambda_j+mu ;;Longleftrightarrow;;$ $;;Longleftrightarrow;; muin {lambda_i-lambda_jmid lambda_i,lambda_jin text{Sp}(A)}.$

Ответ: ${lambda_i-lambda_jmid lambda_i,lambda_jin text{Sp}(A)}.$

Задача 3. Бросается симметричная монета 2021 раз. Обозначим количество гербов. Далее бросается другая симметричная монета 1010 раз. - количество орлов на ней. Найти вероятность того, что .

Решение

Рассмотрим элементарный исход при котором выполняется неравенство . Определим другой элементарный исход полученный из инвертированием монеты на каждом шаге. Тогда . Таким образом,

Значит инвертирование монеты осуществляет биекцию между событием и его дополнением. Откуда следует, что

$P(X>2Y)=frac{1}{2}.$

Ответ: $frac{1}{2}.$

Задача 4. Существует ли многочлен с действительными коэффициентами
а) от одной переменной;
б) от двух переменных,
множество значений которого совпадает с множеством положительных чисел?

Решение

а) Пусть $f(x)=a_nx^n+ldots+a_1x+a_0in mathbb{R}[x]$ — такой многочлен. Тогда и чётно. Следовательно, при . Значит, $inf_mathbb{R} f=inf_{[a,b]} f$ для некоторого отрезка . Но инфимум непрерывной функции на отрезке достигается. Значит, , где $m=min_mathbb{R} f$ .

б) Пример: . Ясно, что при всех и любое достигается при , .

Ответ: а) нет; б) да.

Замечание. Пункт б) — старая фольклорная задача. В разное время она предлагалась на разных олимпиадах. Пункт а) — несложный теоретический факт. Такого рода вопросы типичны для собеседований.

Задача 5. Найдите $minlimits_{mathbf{x,y>0}} (x^y+y^x)$

Решение

Заметим, что если или больше единицы, то

Рассмотрим положительные . Напомним неравенство Бернулли:

при и . Имеем неравенства

$frac{1}{x^y}=left(1 + left(frac{1}{x} - 1right) right)^yleqslant1 + yleft(frac{1}{x} - 1right) < 1 + yfrac{1}{x}=frac{x+y}{x}.$

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

${x^y}> frac{x}{x+y}.$

Из симметрии, получается неравенство

${y^x}> frac{y}{x+y}.$

Значит

${x^y} + {y^x}>1.$

С другой стороны, при очевидно, что ${x^y} + {y^x}=1$ . Таким образом, мы показли, что

$inf_{x,y>0} ({x^y} + {y^x})=1.$

Ответ: .

Задача 6. В треугольник со сторонами бросают точку. Найти вероятность того, что наибольший перпендикуляр, опущенный на стороны, будет опущен на гипотенузу.

Решение

Ясно, что ответ не зависит от масштаба, поэтому можно рассмотреть подобный исходному треугольник со сторонами 3, 5, 4.

Проведём биссектрисы углов треугольника из каждой вершины. Рассмотрим биссектрису . Очевидно, что два перпендикуляра опущенных из любой точки на стороны и равны. Для точки лежащей левее (в треугольнике ) перпендикуляр опущенный на будет меньше перпендикуляра опущенного на . Из этих рассуждений следует, что множество точек таких, что наибольший перпендикуляр опущенный на стороны треугольника ьбудет опущен на гипотенузу совпадает с закрашенной областью. Откуда вытекает, что искомая вероятность равна отношению площадей области и треугольника . Далее найдем площади соответствующих областей.

Площадь треугольника очевидно равна Пробный экзамен в ШАД - 85 . Далее вспомним два простых свойства биссектрисы. Сформулируем их для биссектрисы :

Теорема о биссектрисе треугольника: биссектриса угла треугольника делит противолежащую сторону на отрезки, пропорциональные прилежащим к этому углу сторонам. Следовательно,

$frac{AC’}{C’B}=frac{AC}{BC},quad frac{AB’}{B’C}=frac{AB}{BC}$
Теорема о площадях через центр вписанной окружности: площади треугольников пропорциональны соответствующим сторонам треугольника

$S_{AOB}:S_{AOC}:S_{BOC}=AB:AC:BC$

Из теоремы о площадях сразу находим

$S_{AOB}=2,quad S_{AOC}=frac{3}{2}.$

Если опустить высоту в треугольнике из точки , то легко увидеть, что

$frac{S_{AOC'}}{S_{C'OB}}=frac{AC'}{C'B}=frac{AC}{BC}=frac{3}{5}$

Значит,

$S_{AOC'}=frac{3}{4}.$

Аналогично, находим

$S_{AOB'}=frac{2}{3}$

Окончательно, искомая вероятность равна

$frac{S_{AOC'}+S_{AOB'}}{S_{ABC}}=frac{17}{72}.$

Ответ: $frac{17}{72}.$

Задача 7. Постройте алгоритм, который находит все вершины ориентированного графа, достижимые из всех вершин графа (включая эти), или определяет, что таких вершин нет.

Решение

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

Сначала найдём все компоненты сильной связности ор. графа . Это можно сделать, например, алгоритмом Косарайю или Тарьяна; оба алгоритма основаны на поиске в глубину и работают за врем .

После этого построим граф-конденсат $G^{ast}$ . Его вершинами являются компоненты сильной связности исходного графа. Между двумя компонентами и проводится дуга , если в исходном графе существует хотя бы одно ребро , где . и .

Граф-конденсат всегда является ориентированным ациклическим графом (DAG). Действительно, если бы в графе-конденсате существовал цикл, то все компоненты, лежащие на этом цикле, были бы взаимно достижимы, а значит, должны были бы образовывать в одну компоненту сильной связности. Это противоречит построению конденсата.

Далее рассмотрим стоки графа-конденсата, то есть вершины, из которых не выходит ни одного ребра. Если в графе-конденсате существует ровно один сток , то каждая вершина конденсата имеет путь в этот сток. В самом деле, в любом конечном DAG из любой вершины можно двигаться по исходящим рёбрам до некоторого стока; поскольку сток единственный, этот путь неизбежно заканчивается именно в . Следовательно, из любой компоненты сильной связности исходного графа достижима компонента , а значит, все вершины компоненты достижимы из любой вершины исходного графа. Поэтому именно вершины компоненты являются искомыми. Вершина является стоком, если её список смежности пуст — это условие легко проверяется за .

Если же в графе-конденсате имеется несколько стоков, то искомых вершин не существует. Действительно, пусть и — два различных стока. Из нельзя попасть в , поскольку из вообще не выходит рёбер, и аналогично из нельзя попасть в . Следовательно, не существует компоненты, достижимой из всех остальных компонент, а значит, в исходном графе нет вершины, достижимой из всех вершин графа.

Таким образом, алгоритм имеет следующий вид:

Найти компоненты сильной связности графа.
Построить граф-конденсат $G^{ast}.$
Посчитать число его стоков $G^{ast}.$
Если сток единственный, вернуть все вершины исходного графа, принадлежащие соответствующей компоненте сильной связности.
Если стоков несколько, вернуть пустое множество.

Все этапы выполняются за линейное время. Поиск компонент сильной связности занимает , построение графа-конденсата также требует просмотра всех рёбер исходного графа и занимает , поиск стоков занимает $O(|V^{ast}|)$ , где $V^{ast}$ — вершины графа конденсата; $|V^{ast}| leq |V|$ . Следовательно, итоговая асимптотическая сложность алгоритма равна . Память также линейна относительно размера исходного графа.