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

2024-10-06 в 13:16, admin, рубрики: задачи, линал, матан, математика, поступление, теорвер, ШАД

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

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

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

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

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

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

Задача 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)$

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

Матрицы одного и того же преобразования в двух различных базисах могут отличаться до неузнаваемости, но кое-что общее у них все-таки есть. Неизменными остаются детерминант, он равен произведению собственных значений: и след матрицы (сумма диагональных элементов), тут уже сумма собственных значений: $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$ поворот на

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

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

$A'=S^{-1}AS=begin{pmatrix} 1 & 0 & 0\0 & cosalpha & -sinalpha\ 0 & sinalpha & cosalpha end{pmatrix}$ .

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

Таким образом, . А значит.

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

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

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

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

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

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

$p=frac{1}{2}left(p+frac{2}{p}right)hspace{5pt}Longleftrightarrowhspace{5pt} p^2=2,hspace{3pt} p=pmsqrt{2}.$

А раз все элементы очевидно положительны, то вот вам и в ответе.

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожее вы точно видели при интегрировании по частям. Взять хотя бы .

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

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

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

$displaystyle J=intlimits_{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 intlimits_{pi}^{0}frac{pi-y}{1+sin y}(-dy)=intlimits_{0}^{pi}frac{pi-y}{1+sin y}dy$

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

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

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

Это уже дело нехитрое (например, через замену ), этот интеграл равен .

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

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

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

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

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

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

Математическое ожидание каждой такой величины:.

С другой стороны, интересующая нас случайная величина (, общее число треугольников) – это сумма величин , . То есть мы буквально обходим каждую из 1140 троек вершин и спрашиваем: есть треугольник? Если да (), то добавляем 1, если нет (), то пропускаем. Итак:

$xi=sum^{1140}_{i=0}xi_i$ , $M(xi)=Mleft(sum^{1140}_{i=0}xi_iright)$ .

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

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

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

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

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

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

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

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