27 мая 2012

1. Сколько способов пройти из $(0,0,0)$ в $(n,2n,3n)$, если можно делать шаги на $+1$ по любой из осей?
   Решение
   Число способов разбить множество из $6n$ элементов на множества из $n$, $2n$ и $3n$ элементов равно мультиномиальному коэффициенту $\frac{(6n)!}{n! (2n)! (3n)!}$.
   Решение 2
   Выбираем сначала $n$ шагов по одной из осей из $6n$ возможных: $C_{6n}^n$. Выбираем $2n$ шагов из оставшихся $5n$ шагов: $C_{5n}^{2n}$. Общее число комбинаций равно $C_{6n}^n C_{5n}^{2n} = \frac{(6n)!}{n! (2n)! (3n)!}$.
   Ответ
   $\dfrac{(6n)!}{n! (2n)! (3n)!}$.
2. Найти $f^{(319)} (0)$, если $f(x) = \frac{x^2+17}{x^4 - 5x^2+4}$.
   Решение
   Заметим, что функция $f(x)$ — четная. Это означает, что в ее ряде Тейлора есть только члены с четными степенями. Тогда производная нечетного порядка не содержит нулевого члена и $f^{(319)} (0) = 0$.
   Ответ
   $0$.
3. Сколько перестановок коммутируют с $(123)(456)$?
   Решение
   В задаче требуется найти число различных наборов $a,b,c,d,e,f$ таких, что выполнено $$\begin{pmatrix}1&2&3&4&5&6\\b&c&a&e&f&d\end{pmatrix} = \begin{pmatrix}1&2&3&4&5&6\\a&b&c&d&e&f\end{pmatrix} \begin{pmatrix}1&2&3&4&5&6\\2&3&1&5&6&4\end{pmatrix}.$$ Заметим, что, например, утверждение $a=1$ полностью задает весь цикл ($a=1$, $b=2$, $c=3$). Подставляя другие значения $a$ убеждаемся, что на местах $a,b,c$ может быть либо циклическая перестановка $1,2,3$, либо циклическая перестановка $4,5,6$. Проведя аналогичные рассуждения для $d,e,f$ получим, что число всех возможных наборов равно $2 \cdot 3^2 = 18$.
   Примечание. Точно так же можно доказать и более общее утверждение. Если перестановка состоит из циклов, различные длины которых равны $n_1, n_2, \ldots, n_k$ и каждая длина $n_i$ встречается $m_i$ раз, то число перестановок, которые с ней коммутируют, равно $$\prod\limits_{i=1}^k m_i! \: n_i^{m_i}.$$
   Ответ
   $18$.
4. В равностороннем треугольнике $ABC$ площади $1$ выбираем точку $M$. Найти математическое ожидание площади $ABM$.
   Решение
   Заметим, что $M(S_{ABM} + S_{BCM} + S_{CAM}) = 1$. Тогда из линейности матожидания и равенства матожиданий площадей треугольников $ABM$, $BCM$ и $CAM$ получим $M(S_{ABM}) = \frac13$.
   Решение 2
   Площадь треугольника $ABM$ равна нулю, когда $M$ лежит на $AB$, равна $1$, когда $M$ совпадает с $C$ и линейна по расстоянию от точки $M$ до стороны $AB$. Поэтому матожидание площади $ABM$ равно объему пирамиды высотой $1$, опирающейся на треугольник $ABC$. Объем такой пирамиды равен $\frac13$.
   Ответ
   $\dfrac13$.
5. Вычислите интеграл $\int \frac{1}{\sqrt{1 + e^x}} dx$.
   Решение
   Сделаем замену $t=\sqrt{1 + e^x}$. Тогда $$\int \frac{dx}{\sqrt{1+e^x}} = \int \frac{2 dt}{t^2 - 1} = \int \left( \frac{1}{t-1} - \frac{1}{t+1} \right) dt = \ln \frac{|t-1|}{|t+1|} + C.$$ Сделав обратную замену, получаем $$\int \frac{dx}{\sqrt{1+e^x}} = \ln \frac{\sqrt{1+e^x} - 1}{\sqrt{1+e^x} + 1} + C.$$ Примечание. Ответ можно также записать в виде $$\int \frac{dx}{\sqrt{1+e^x}} = -2\, \textrm{arcth}\, (\sqrt{1+e^x}) + C,$$ где $\textrm{arcth}$ — гиперболический арккотангенс.
   Ответ
   $\ln \dfrac{\sqrt{1+e^x} - 1}{\sqrt{1+e^x} + 1} + C$.
6. Показать, что у целочисленной матрицы не бывает рациональных нецелых собственных чисел.
   Решение
   Предположим, что у такой матрицы есть рациональное целое собственное значение в виде несократимой дроби $p/m$. Подставим его в характеристическое уравнение на собственные значения матрицы: $$\left( \frac{p}{m} \right)^n + a_{n-1} \left( \frac{p}{m} \right)^{n-1} + \cdots + a_0 = 0.$$ Домножим все члены этого уравнения на $m^{n-1}$: $$\frac{p^n}{m} + a_{n-1} p^{n-1} + \cdots + a_0 m^{n-1} = 0.$$ Заметим, что в этом уравнении только одно нецелое слагаемое $\frac{p^n}{m}$, чего быть не может.
7. Есть круговая трасса, на которой в некоторых местах стоят бензоколонки. Расстояние между ними и количество бензина на каждой бензоколонке известны. Имеется также машина с постоянным и известным расходом топлива. Предложите алгоритм, работающий за $O(n)$ по времени, который позволяет найти ту бензоколонку, начиная с которой можно проехать всю трассу, или сказать, что такой нет.
   Решение
   Пронумеруем бензоколонки по порядку начиная с произвольной. Пусть теперь $g[i]$ — изменение количества топлива после заправки в $i$-ой бензоколонки и прохождения дороги после нее. Тогда если $\sum\limits_{i=1}^n g[i] < 0$ такой бензоколонки нет, поскольку в таком случае количество топлива в бензоколонках меньше, чем требуется для прохождения всех дорог. Покажем, что если $\sum\limits_{i=1}^n g[i] \geqslant 0$ такая бензоколонка существует всегда. Рассмотрим частичные суммы $h[k] = \sum\limits_{i=1}^k g[i]$. Пусть минимальная частичная сумма достигается в индексе $j$ и равна $h[j]$. Тогда если $h[j] \geqslant 0$, то задача решена. Если же нет — начнем движение с бензоколонки, следующей за $j$. В таком случае частичные суммы всегда неотрицательны, поскольку в противном случае $j$ не был элементом, в котором достигается минимальная частичная сумма. Сложность по времени — $O(n)$.