Математика и ШАД / forpes.ru

Главная
Математика и ШАД

Математика и ШАД +1

06.10.2024 13:16

Zhestkov 1 465 Источник

Осень – самое подходящее время для старшекурсников, чтобы задуматься о планах на следующий учебный год. Вступительные и олимпиады обычно проходят в конце весны/начале лета и есть время для того, чтобы основательно подготовиться. Тем более что экзамены бывают очень непростыми, как, например, в Школу Анализа Данных (ШАД) Яндекса. При поступлении понадобится очень уверенное владение математикой: задачи экзамена носят олимпиадный характер и для успеха мало знаний, нужна еще хорошая насмотренность

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

Идея первая. Для поиска детерминанта приводить матрицу к верхнетреугольному виду

Начнем с самого простого (и при этом очень распространенного) приема. Частый гость на различных студенческих олимпиадах и вступительных – детерминант произвольного порядка . Есть не так много способов его нахождения. Можно, например, начать раскрывать по строке/столбцу, а дальше обнаружить некоторую закономерность и подключить математическую индукцию. Классика здесь – определитель Вандермонда.

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

добавление к одной строке/столбцу другой, умноженной на число: $\det A$ не меняется;
умножение строки/столбца на число $\alpha\neq0$ : $\det A$ умножается на $\alpha$ ;
перестановка двух строк/столбцов местами: $\det A$ меняет знак.

Задача 1. Найти детерминант:

$\det A=\left|\begin{array}{rrcrr} 5 & 5 & \ldots & 5 & 2\\ 5 & 5 & \ldots & 2 & 5\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 5 & 2 & \ldots & 5 & 5\\ 2 & 5 & \ldots & 5 & 5 \end{array} \right|$

Решение: Для начала переместим двойки на главную диагональ. Для этого нужно менять столбцы местами – последний на первое место, предпоследний – на второе, и так далее. Но сколько таких перестановок потребуется? Менять указанным образом – проблемно, мы же не знаем: четное число столбцов, или нет. Сделаем так: представьте, что столбцы это люди в очереди, а касса стоит слева. Последнему нужно попасть на первое место, для этого он последовательно извинится перед человеком впереди. Предпоследний, оказавшись теперь последним, должен стать вторым. Для этого он потревожит уже человек. И так далее, получаем, что общее число перестановок равно сумме первых натуральных чисел: , итак:

$\det A=(-1)^{\frac{n(n-1)}{2}}\left|\begin{array}{rrcrr} 2 & 5 & \ldots & 5 & 5\\ 5 & 2 & \ldots & 5 & 5\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 5 & 5 & \ldots & 2 & 5\\ 5 & 5 & \ldots & 5 & 2 \end{array} \right|$

Теперь из всех строчек, кроме первой, вычтем строку предыдущую. Так сгенерируем кучу нулей, а детерминант никак не изменится. Получим:

$\det A=(-1)^{\frac{n(n-1)}{2}}\left|\begin{array}{rrcrr} 2 & 5 & \ldots & 5 & 5\\ 3 & -3 & \ldots & 0 & 0\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 3 & 0 & \ldots & -3 & 0\\ 3 & 0 & \ldots & 0 & -3 \end{array} \right|$

Уже почти верхнетреугльный вид! Мешают только тройки в первом столбце. И ничего: добавим к первому столбцу каждый из оставшихся: минус тройки сделают свое дело, а детерминант не изменится

$\det A=(-1)^{\frac{n(n-1)}{2}}\left|\begin{array}{crcrr} 5n-3 & 5 & \ldots & 5 & 5\\ 0 & -3 & \ldots & 0 & 0\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 0 & 0 & \ldots & -3 & 0\\ 0 & 0 & \ldots & 0 & -3 \end{array} \right|$

Вот и ответ: $\det A=(-1)^{\frac{n(n-1)}{2}}\cdot(-3)^{n-1}\cdot(5n-3)$

Идея вторая. Использовать инварианты матрицы преобразования

Матрицы одного и того же преобразования в двух различных базисах могут отличаться до неузнаваемости, но кое-что общее у них все-таки есть. Неизменными остаются детерминант, он равен произведению собственных значений: $\det A=\lambda_1\cdot\lambda_2\cdot\dots\cdot\lambda_n$ и след матрицы (сумма диагональных элементов), тут уже сумма собственных значений: $\mathrm{tr} A=\lambda_1+\lambda_2+\dots+\lambda_n$ . Эти инварианты лежат в основе решений многих задач. Рассмотрим, например, такую

Задача 2. Известно, что матрица $A=\begin{pmatrix} -5 & 7 & 74\\2 & 1 & -20\\ 0 & 2 & 5 \end{pmatrix}$ задает в $\mathbb{R}^3$ поворот на

некоторый угол $\alpha$ . Найти угол $\alpha$ .

Решение: давайте поступим так: запишем матрицу в базисе, в котором вектор $\mathbf{e}_1$ направлен вдоль оси вращения, а два оставшихся вектора – $\mathbf{e}_2$ и $\mathbf{e}_3$ дополняют его до ортонормированного базиса в $\mathbb{R}^3$ . В этом случае матрица преобразования примет вид:

$A'=S^{-1}AS=\begin{pmatrix} 1 & 0 & 0\\0 & \cos\alpha & -\sin\alpha\\ 0 & \sin\alpha & \cos\alpha \end{pmatrix}$ .

Вспомним теперь, что след матрицы сохранился:

$\mathrm{tr}A=(-5)+1+5=\mathrm{tr}A'=1+2\cos\alpha$

Таким образом, $1+2\cos\alpha=1, \cos\alpha=0$ . А значит $\alpha=90^\circ$ .

Идея третья. Использовать теорему Вейерштрасса для поиска предела последовательности

Сама теорема звучит так: если последовательность монотонно возрастает (убывает), и ограничена сверху (снизу), то последовательность имеет конечный предел, равный супремуму (инфимуму) множества своих значений. Если убрать слова про ограниченность, то пределы тоже будут, только бесконечные. В отличие от арифметических свойств и теоремы о полицейских, теорема Вейерштрасса ценна именно для доказательств существования пределов

Задача 3. Найти $\lim\limits_{n\to \infty}a_n$ , если $a_{n+1}=\frac{1}{2}\left(a_n+\frac{2}{a_n}\right), a_1=1$

Решение: выпишем несколько первых элементов:

$a_1=1, a_2=1,5, a_3\approx 1,417, a_4\approx 1,414,...$

Что-то напоминает, не правда? Тут проявляется $\sqrt{2}$ , он и в самом деле будет ответом. Но почему?

Часто доводилось видеть такое решение: а давайте просто предельный переход применим в рекуррентом соотношении! Получим:

$p=\frac{1}{2}\left(p+\frac{2}{p}\right)\hspace{5pt}\Longleftrightarrow\hspace{5pt} p^2=2,\hspace{3pt} p=\pm\sqrt{2}.$

А раз все элементы очевидно положительны, то вот вам и $\sqrt{2}$ в ответе.

Боюсь, что за такое решение (даже не лишенное смысла и даже с правильным ответом), на вступительных поставили бы ноль баллов. Почему? Проблема в самом рекуррентном переходе: осуществляя его, мы подразумеваем, что предел точно есть. А вдруг последовательность расходится? Тогда такое рассуждение просто лишено смысла (в качестве упражнения можете придумать пример). Тут-то нам и поможет Вейерштрасс! Мы аккуратно покажем, что последовательность ограничена снизу и монотонно убывает (делаю такие предположения из выписанных элементов).

$\bullet$ Ограниченность снизу: по условию: $a_{n+1}=\frac{a_n+2/a_n}{2}$ . Это среднее

арифметическое чисел и . Оно, по неравенству о средних, больше или равно среднего геометрического (корня из произведения этих же чисел), получаем:

$a_{n+1}=\frac{a_n+2/a_n}{2}\geqslant\sqrt{a_n \cdot \frac{2}{a_n}}=\sqrt{2}$

Таким образом, начиная с , все элементы больше или равны $\sqrt{2}$ . Ограниченность снизу доказана.

$\bullet$ Монотонность: покажем, что последовательность убывает. Из условия:

$a_{n+1}=\frac{a_n}{2}\left(1+\frac{2}{a^2_n}\right)$ . Из пункта про ограниченность мы знаем, что начиная со

второго номера $a_n\geqslant\sqrt{2}$ , а значит дробь в скобке меньше или равна единице, а вся скобка меньше или равна двум. Таким образом, $a_{n+1}\leqslant a_n$ , и монотонность доказана.

И вот теперь, благодаря Вейерштрассу, мы уверены, что предел есть, рекуррентный переход корректен, а ответ $\sqrt{2}$ не только правильный, но и принесет баллы за эту задачу.

Чаще всего теорема Вейерштрасса применяется для поиска пределов последовательностей, заданных рекуррентно. Но работает и с явно заданными (ведь мы часто можем сами соорудить рекуррентный способ задания).

Идея четвертая. Замена переменной в интеграле, порождающая исходный интеграл

Суть простая. Есть, например, определенный интеграл, обозначим его . В некоторых случаях можно подобрать замену таким образом, чтобы после замены интеграл снова возник, теперь в качестве слагаемого со знаком минус. Тогда получим равенство:

$J=\text{*easy integral*}-J$ , из него $J=\frac{\text{*easy integral*}}{2}$ .

Похожее вы точно видели при интегрировании по частям. Взять хотя бы $\displaystyle \int e^x\cos xdx$ .

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

Задача 4. Найти $\displaystyle J= \int\limits_{0}^{\pi}\frac{x}{1+\sin x}dx$

Решение: сделаем замену $y=\pi-x$ . И сразу разберемся почему. Причин две: во-первых, $\sin y=\sin x$ по формулам приведения, получается некоторый инвариант. Во-вторых, пределы интегрирования просто поменяются при такой замене местами (что легко исправляется знаком "минус" перед интегралом). Итак, получаем:

$\displaystyle J= \int\limits_{0}^{\pi}\frac{x}{1+\sin x}dx=\left|\begin{array}{c} y=\pi-x \\ dx=-dy \\ \sin x=\sin y \end{array}\right|=\displaystyle \int\limits_{\pi}^{0}\frac{\pi-y}{1+\sin y}(-dy)=\int\limits_{0}^{\pi}\frac{\pi-y}{1+\sin y}dy$

А последний интеграл разбиваем на два слагаемых:

$\displaystyle J= \int\limits_{0}^{\pi}\frac{\pi-y}{1+\sin y}dy=\int\limits_{0}^{\pi}\frac{\pi}{1+\sin y}dy-\int\limits_{0}^{\pi}\frac{y}{1+\sin y}dy.$

Узнаете второе слагаемое? Это же наш интеграл ! Остается найти $\int\limits_{0}^{\pi}\frac{\pi}{1+\sin y}dy$ .

Это уже дело нехитрое (например, через замену $t= \mathrm{tg}(y/2)$ ), этот интеграл равен $2\pi$ .

Тогда $J=2\pi-J$ , и в итоге $J=\pi$ . Видеоразбор этой задачи (и еще пары крутых интегралов) можно найти в ролике на моем YouTube-канале.

Идея пятая. Использовать индикаторные случайные величины

В задачах на дискретные случайные величины часто бывает полезно ввести индикаторную случайную величину. Она принимает только два значения: 1 (условный "успех") и 0 (иначе). Прелесть в том, что у такой величины легко ищется математическое ожидание: оно просто равно вероятности "успеха". А если добавить к этому свойство линейности математического ожидания... Давайте рассмотрим на примере.

Задача 5. В простом графе 20 вершин. Вероятность наличия ребра между любыми двумя вершинами одинакова и равна . Найти математическое ожидание числа треугольников в это графе.

Решение: для начала посчитаем сколько всего треугольников может быть в графе. Это число способов выбрать три неупорядоченные вершины: $C_{20}^{3}=1140$ . Введем случайную величину $\xi_i$ для отдельной тройки вершин (всего 1140, по числу троек вершин, случайных величин с одним и тем же распределением):

$\xi_i=\begin{cases} 1, \hspace{4pt}\text{если все три ребра на месте;}\\ 0,\hspace{4pt} \text{иначе} \end{cases}, \hspace{5pt} i=\overline{1\dots1140}$

Математическое ожидание каждой такой величины: $M(\xi_i)=P(1)=p^3=0,216$ .

С другой стороны, интересующая нас случайная величина ( $\xi$ , общее число треугольников) – это сумма величин $\xi_i$ , $i=\overline{1\dots1140}$ . То есть мы буквально обходим каждую из 1140 троек вершин и спрашиваем: есть треугольник? Если да ( $\xi_i=1$ ), то добавляем 1, если нет ( $\xi_i=0$ ), то пропускаем. Итак:

$\xi=\sum^{1140}_{i=0}\xi_i$ , $M(\xi)=M\left(\sum^{1140}_{i=0}\xi_i\right)$ .

А тут вступает в игру линейность математического ожидания! И сразу ответ

$M(\xi)=M\left(\sum^{1140}_{i=0}\xi_i\right)=\sum^{1140}_{i=0}M(\xi_i)=1140\cdot0,216=246,24$ .

Задачи для закрепления:

Задача 1 (ШАД-2015) Найдите определитель матрицы $A=(a_{ij})$ , где $a_{ij}=C_{i+j-2}^{i-1}$ .

Задача 2. (ШАД-2015) Пусть и – квадратные вещественные матрицы одного и того же размера. Докажите, что $\det(E-AB)=\det(E-BA)$ .

Задача 3 (ШАД-2015) Найти $\lim\limits_{n\to \infty}a_n$ , если $a_{n+1}=\frac{a_n^2(a_n-3)}{4}, a_0=-\frac{1}{2}$ .

Задача 4 (ШАД-2015) Вычислить интеграл $\int\limits_{\frac{1}{3}}^{3}\frac{\mathrm{arctg}x}{x^2-x+1}dx$

Задача 5 (ШАД-2016) В ряд расположены предметов. Случайно выбираются предметов, . Случайная величина равна количеству таких предметов , что выбран, а все его соседи не выбраны. Найдите математическое ожидание .

Ответы: 1) ; 3) ; 4) $\frac{\pi}{2\sqrt{3}}\mathrm{arctg}4\sqrt{3}$ ; 5) $M=2\cdot\frac{C_{m-2}^{k-1}}{C^k_m}+(m-2)\cdot\frac{C_{m-3}^{k-1}}{C_m^k}$

Можете делиться своими мыслями по задачам в комментариях, обсудим :)

Автор статьи: Сергей Жестков, ex-преподаватель МФТИ, OTUS; основатель курсов по математике Zhestkov University

Комментарии (1)

MasterMentor
06.10.2024 14:32
#27384196
+1
Олимпиадники - срецифичная прослойка: у подавляющего большинства детей заниматься такой математикой - мотивации нет (она капитально оторвана от их практики).

О ШАД много полярных мнений, от восторга до:

А что же Яндекс? Что у них есть хорошего кроме ШАД (уровня сельской школы 19 века)?

Стал интересоваться направлением data science. Это просто распиаренное го*но или действительно годная тема? Хайп. Нужно, но далеко не всем кто в хайп попал.

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

В общем, нужен какой-то новый, более весёлый ШАД.

Математика и ШАД +1

Комментарии (1)

MasterMentor