Студенческая олимпиада киевского мехмата 2007

[dm]

Открытая студенческая олимпиада
механико-математического факультета
22 февраля 2007 года
Задачи для 1--2 курсов

1. Пусть $p,q,r,s$ --- натуральные числа. Вычислить предел

$$\lim\limits_{n\to\infty}\prod\limits_{k=1}^n\frac{(k+p)(k+q)}{(k+r)(k+s)}.$$

2. При всех ли $n\ge2$ число

$$\sum\limits_{k=1}^nkC_{2n}^k$$

делится на 8?

3. Двое игроков по очереди заменяют звездочки в матрице
$\left(\begin{smallmatrix}* &* & \ldots & * \\ * &* & \ldots & * \\ \ldots & \ldots & \ldots& \ldots \\ * & * &\ldots & * \\ \end{smallmatrix}\right)$ размера $10\times10$ натуральными числами от 1 до 100
(на каждом шаге разрешается ставить произвольное еще
неиспользованное число вместо произвольной звездочки). Если
полученная матрица оказывается невырожденной, то выигрывает первый
игрок, а если вырожденной, то второй. Имеет ли кто-то из игроков
выигрышную стратегию? Если имеет, то кто?

4. Доказать, что функция $f\in C^1\bigl((0,+\infty)\bigr),$
удовлетворяющая соотношению

$$f'(x)=\frac{1}{1+x^4+\cos f(x)},\ x>0,$$

ограничена на $(0,+\infty).$

5. Существует ли многочлен, принимающий значение $k$ ровно в $k$
точках при всех $1\le k\le 2007$?

6. Циферблат часов является кругом радиуса 1. Часовая стрелка имеет
вид круга радиуса 1/2, касающегося внутренним образом круга
циферблата, а минутная стрелка является отрезком длины 1. Найти
площадь фигуры, образуемой всеми возможными пересечениями стрелок в
течение полусуток (т.е. за один полный оборот часовой стрелки).

7. Найти наибольшее значение выражения $x_1^3+\ldots+x_{10}^3$ при
$x_1,\ldots,x_{10}\in[-1,2]$ и $x_1+\ldots+x_{10}=10.$

8. Пусть $a_0=1,$ $a_1=1$ и $a_n=a_{n-1}+(n-1)a_{n-2},\, n\ge2.$
Доказать, что для всех нечетных чисел $p$ число $a_p-1$ делится на
$p.$

9. Найти все натуральные $n$, для которых существует бесконечно
много матриц $A$ размера $n\times n$ с целыми элементами, таких, что
$A^n=I$, где $I$ --- единичная матрица.

Открытая студенческая олимпиада
механико-математического факультета
22 февраля 2007 года
Задачи для 3--4 курсов

1. Исследовать на сходимость несобственный интеграл Римана

$$\int\limits_0^{\infty}\frac{\sin x\,dx}{x+\ln x}.$$

2. Циферблат часов является кругом радиуса 1. Часовая стрелка имеет
вид круга радиуса 1/2, касающегося внутренним образом круга
циферблата, а минутная стрелка является отрезком длины 1. Найти
площадь фигуры, образуемой всеми возможными пересечениями стрелок в
течение полусуток (т.е. за один полный оборот часовой стрелки).

3. Доказать, что функция $f\in C^1\bigl((0,+\infty)\bigr),$
удовлетворяющая соотношению

$$f'(x)=\frac{1}{1+x^4+\cos f(x)},\ x>0,$$

ограничена на $(0,+\infty).$

4. Существует ли многочлен, принимающий значение $k$ ровно в $k$
точках при всех $1\le k\le 2007$?

5. Пусть функция $f:\mathbb{R}\to [0,+\infty)$ измерима по Лебегу и
такая, что $\int_Afd\lambda<+\infty$ для любого множества $A$ с
$\lambda(A)<+\infty$ ($\lambda$ --- мера Лебега). Доказать, что
существуют константа $M$ и интегрируемая по Лебегу функция
$g:\mathbb{R}\to [0,+\infty)$, такие, что $f(x)\le g(x)+M$ при всех
$x\in \mathbb{R}$.

6. Исследовать на монотонность функцию

$$f(\sigma)=\mathsf{M}\frac{1}{1+e^\xi},\, \sigma>0,$$

где $\xi$
--- гауссовская случайная величина со средним $m$ и дисперсией
$\sigma^2,$ $m$ --- действительный параметр.

7. Найти наибольшее значение выражения $x_1^3+\ldots+x_{10}^3$ при
$x_1,\ldots,x_{10}\in[-1,2]$ и $x_1+\ldots+x_{10}=10.$

8. Пусть $A$, $B$ --- симметричные действительные положительно
определенные матрицы, причем матрица $A+B-E$ также положительно
определена. Может ли быть отрицательно определенной матрица

$$A^{-1}+B^{-1}-\frac{1}{2}(A^{-1}B^{-1}+B^{-1}A^{-1})?$$

9. Пусть $P(z)$ --- многочлен со старшим коэффициентом 1. Доказать,
что на единичном круге $\{z\in\mathbb{C}: |z|=1\}$ существует такая
точка $z_0,$ для которой $|P(z_0)|\ge1.$

[Руст]

Первая задача не совсем корректно сформулирована. При p+q<r+s предел равен нулю. При p+q=r+s предел r!s!/(p!q!), при p+q>r+s предел не существует, точне стремится к бесконечности.

[RIP]

2)

$$\sum_{k=1}^nk\binom{2n}k=2n\sum_{k=0}^{n-1}\binom{2n-1}k=n2^{2n-1}$$

Добавлено спустя 18 минут 38 секунд:

9) (3-4 курс)
Если

$$\max_{|z|=1}|P(z)|<1,$$

то, по теореме Руше, многочлен $z^n-P(z)$ имеет ровно $n$ корней в круге $|z|<1$. Противоречие.

Либо так: воспользоваться принципом максимума модуля для функции $z^nP(1/z)$

[Руст]

Задача 7 повторяется дважды. Взяв две переменные x и у c фиксированной суммой a, получаем, что максимум суммы кубов достигается тогда, когда хотя бы одна из переменных на границе (еcли а>=0) или когда они равны, если a<0. Отсюда получается, что максимум достигается, когда 6 переменных равны 2, а остальные 4 равны -1/2. Соответственно максимальное значение равно 48-1/2=95/2.

[RIP]

4) (1-2 к.)
Ограниченность на $[1;\infty)$ очевидна.
Допустим, что $f(+0)=-\infty$ ($f'(x)>0\Rightarrow f(x)$ возрастает). Берём точки $0<a<b<1$ такие, что $0>f(b)=f(a)+2\pi n,\ n\in\mathbb{N}$.
Имеем

$$1>b-a=\int\limits_a^b((1+x^4)f'(x)+(\sin f(x))')\,dx=\int\limits_a^b(1+x^4)f'(x)\,dx=$$

$$=(1+b^4)f(b)-(1+a^4)f(a)-4\int\limits_a^bx^3f(x)\,dx>(1+b^4)f(b)-(1+a^4)f(a)$$

Беря $a\to+0$ (следовательно, $f(a)\to-\infty$), получаем противоречие.

Добавлено спустя 2 часа 9 минут 45 секунд:

5) (1-2 к.)
Если рассматривать многочлен над полем $\mathbb{R}$, то ответ положительный.
Рассмотрим многочлен $f_0(x)$ степени $\leqslant2005$, удовлетворяющий условиям $f_0(x)=x,\ f_0'(x)=0$ при $x=2,4,6,\ldots,2006$. Будем искать искомый многочлен в виде $f(x)=f_0(x)+axg(x)$, где $g(x)=(x-2)^2(x-4)^2\ldots(x-2006)^2$. Выберем $a>0$ так, чтобы выполнялось $f(x)>2007$ при $x=1,3,5,\ldots,2005$. Докажем, что многочлен $f(x)$ удовлетворяет условию.
Во-первых, для любого $k=\overline{1,1002}\qquad\max\limits_{[2k;2k+2]}f(x)$ достигается во внутренней точке отрезка $x_k\in(2k;2k+2)$ (т.к. $f(2k)<2007,\ f(2k+2)<2007,\ f(2k+1)>2007$), поэтому $f'(x_k)=0$.
Далее, $\lim\limits_{x\to-\infty}f(x)=-\infty$, поэтому существует $t<1$ такое, что $f(t)<2007$. Тогда найдется $x_0\in(t;2)$ такое, что $f'(x_0)=0$.
Но тогда многочлен степени $2006$ $f'(x)$ имеет $2006$ различных корней $x_0,2,x_1,4,x_2,\ldots,x_{1002},2006$, т.е. имеет вид $f'(x)=2007a(x-x_0)(x-2)\ldots(x-2006)$.
Осталось нарисовать картинку и убедиться, что $f(x)$ удовлетворяет условию.

[RIP]

8) (1-2 к.)
Обозначим $b_n=\frac{a_n}{n!}$. Тогда $b_0=b_1=1$ и $nb_n=b_{n-1}+b_{n-2}$, $n\geqslant2$. Если обозначить $f(x)=\sum_{n=0}^{\infty}b_nx^n$, то $f'(x)=(1+x)f(x)$, откуда

$$f(x)=\exp(x+\frac{x^2}2)=\sum_{m=0}^{\infty}\frac{(x+\frac{x^2}2)^m}{m!}=\sum_{m=0}^{\infty}\sum_{k=0}^{m}\frac{x^{m+k}}{k!(m-k)!2^k}.$$

Отсюда

$$a_n=\sum_{m+2k=n}\frac{n!}{m!k!2^k}=\sum_{m+2k=n}\binom nm(2k-1)!!\text{ (это легко проверить и непосредственно)}$$

Пусть $n$ нечетно, $p$ - простое и $p^{\alpha}||n$. $p$ входит в $\frac{n!}{m!k!2^k}$ в степени

$$\sum_{t=1}^{\infty}\left(\lfloor\frac n{p^t}\rfloor-\lfloor\frac m{p^t}\rfloor-\lfloor\frac k{p^t}\rfloor\right)$$

Если $k>0$ и $t\leqslant\alpha$, то

$$\lfloor\frac n{p^t}\rfloor-\lfloor\frac m{p^t}\rfloor-\lfloor\frac k{p^t}\rfloor=\frac n{p^t}-\lfloor\frac m{p^t}\rfloor-\lfloor\frac k{p^t}\rfloor=$$

$$=\frac{m+2k}{p^t}-\lfloor\frac m{p^t}\rfloor-\lfloor\frac k{p^t}\rfloor>0.$$

Значит, при $k>0\qquad n|\frac{n!}{m!k!2^k}$, поэтому

$$a_n\equiv1\pmod n.$$

Блин, можно было гораздо проще.

$$\frac1n\cdot\frac{n!}{m!k!2^k}=\binom{m+k}k\frac{(n-1)!}{(m+k)!2^k}\in\mathbb{Z}$$

Добавлено спустя 1 час 55 минут 52 секунды:

№5 (3-4 к.)
Обозначим $A_c=\{x\in\mathbb{R}\mid f(x)>c\}$.
Докажем, что существует $M$ такое, что $\lambda(A_M)<\infty$. Допустим противное. Возьмем $B_1\subset A_2$, $\lambda B_1=\frac12$. Если $B_1,\ldots,B_{n-1}$ выбраны, то возьмем $B_n\subset A_{2^n}\setminus(B_1\cup B_2\cup\ldots\cup B_{n-1})$, $\lambda B_n=2^{-n}$. Положим $A=\cup\limits_{n}B_n$. Тогда $\lambda A=1$ и

$$\int\limits_Af(x)\,d\lambda=\sum_n\int\limits_{B_n}f(x)\,d\lambda\geqslant\sum_n1=\infty.$$

Противоречие. Значит, $\exists M\quad\lambda(A_M)<\infty$. Тогда

$$f(x)\leqslant M+f(x)\chi_{A_M}(x).$$

[Руст]

RIP писал(а):

8) (1-2 к.)
Блин, можно было гораздо проще.

$$\frac1n\cdot\frac{n!}{m!k!2^k}=\binom{m+k}k\frac{(n-1)!}{(m+k)!2^k}\in\mathbb{Z}$$

Это неверно. Например m=2,k=1,n=4. Чтобы это выражение стало целым надо умножить на 2 в степени (k+1)/2 (гарантированная степень). Но это не важно, так как речь идёт о подсчёте по модулю нечётного простого числа р. И способ получения формулы для a(n) не совсем корректен. Производящая функция может нигде не сходится за исключением 0 (на самом деле так и есть).

[RIP]

Руст писал(а):

RIP писал(а):

8) (1-2 к.)
Блин, можно было гораздо проще.

$$\frac1n\cdot\frac{n!}{m!k!2^k}=\binom{m+k}k\frac{(n-1)!}{(m+k)!2^k}\in\mathbb{Z}$$

Это неверно. Например m=2,k=1,n=4.

Для нечетного $n$ это верно, т.к. с одной стороны в знаменателе нету двойки (т.к. число вида $\frac an$), а с другой стороны в знаменателе нету нечетных простых (т.к. число вида $\frac b{2^k}$)

Руст писал(а):

И способ получения формулы для a(n) не совсем корректен. Производящая функция может нигде не сходится за исключением 0 (на самом деле так и есть).

Я рассматриваю производящую функцию для $b_n=\frac{a_n}{n!}=o(1)$.

[Хорхе]

RIP писал(а):

Я рассматриваю производящую функцию для $b_n=\frac{a_n}{n!}=o(1)$.

Это вроде бы называется экспоненциальной производящей функцией.

Кстати, насчет расходимости ряда. Что, теорию формальных степенных рядов кто-то отменил?

[RIP]

dm писал(а):

Задачи для 1--2 курсов
3. Двое игроков по очереди заменяют звездочки в матрице
$\left(\begin{smallmatrix}* &* & \ldots & * \\ * &* & \ldots & * \\ \ldots & \ldots & \ldots& \ldots \\ * & * &\ldots & * \\ \end{smallmatrix}\right)$ размера $10\times10$ натуральными числами от 1 до 100
(на каждом шаге разрешается ставить произвольное еще
неиспользованное число вместо произвольной звездочки). Если
полученная матрица оказывается невырожденной, то выигрывает первый
игрок, а если вырожденной, то второй. Имеет ли кто-то из игроков
выигрышную стратегию? Если имеет, то кто?

Понятно, что второй выигрывает. Если первый ставит число $k$ на место $(i,j)$, то второй ставит $101-k$ в клетку $(i-1,j)$, если $i$ четно, и в клетку $(i+1,j)$, если $i$ нечетно.

Добавлено спустя 18 минут 44 секунды:

dm писал(а):

Задачи для 1--2 курсов
6. Циферблат часов является кругом радиуса 1. Часовая стрелка имеет
вид круга радиуса 1/2, касающегося внутренним образом круга
циферблата, а минутная стрелка является отрезком длины 1. Найти
площадь фигуры, образуемой всеми возможными пересечениями стрелок в
течение полусуток (т.е. за один полный оборот часовой стрелки).

Пусть минутная стрелка отклонилась на угол $2\pi\varphi$ ($\varphi\in[0;1)$). Ему соответствуют положения часовой стрелки $\psi=\frac{\pi}6(\varphi+k)\pmod{2\pi}$, $k\in\mathbb{Z}$. Наибольшая длина пересечения соответствует минимальному значению $|2\pi\varphi-\psi|=\frac{\pi}6\|11\varphi\|$ и равна $\cos\frac{\pi\|11\varphi\|}6$
Поэтому искомая площадь равна

$$\pi\int\limits_0^1\cos^2\frac{\pi\|11\varphi\|}6\,d\varphi=\pi\int\limits_0^1\cos^2\frac{\pi\|\varphi\|}6\,d\varphi=2\pi\int\limits_0^{1/2}\cos^2\frac{\pi\varphi}6\,d\varphi=\pi(1/2+3/{(2\pi)})=\frac{\pi+3}2.$$

По-любому где-нибудь наврал.

Добавлено спустя 13 минут 53 секунды:

dm писал(а):

Задачи для 1--2 курсов
9. Найти все натуральные $n$, для которых существует бесконечно
много матриц $A$ размера $n\times n$ с целыми элементами, таких, что
$A^n=I$, где $I$ --- единичная матрица.

При $n\geqslant2$. Например, можно взять $A=C^mBC^{-m}$, где $b_{ij}=\delta_{i\sigma(j)}$, где $\sigma=(12\ldots n)\in\mathfrak{S}_n$ (подстановка), $m\in\mathbb{Z}$ и

$$c_{ij}=\begin{cases}1,&j\geqslant i;\\0,&j<i.\end{cases}$$

Добавлено спустя 14 минут 15 секунд:

dm писал(а):

Задачи для 3--4 курсов
1. Исследовать на сходимость несобственный интеграл Римана

$$\int\limits_0^{\infty}\frac{\sin x\,dx}{x+\ln x}.$$

Человеку, который не сможет исследовать этот интеграл на сходимость, нечего делать на механико-математическом факультете.

dm писал(а):

8. Пусть $A$, $B$ --- симметричные действительные положительно
определенные матрицы, причем матрица $A+B-E$ также положительно
определена. Может ли быть отрицательно определенной матрица

$$A^{-1}+B^{-1}-\frac{1}{2}(A^{-1}B^{-1}+B^{-1}A^{-1})?$$

(Приводимое ниже "решение" неверно.)

$$0<A^{-1}(A+B-E)B^{-1}+B^{-1}(A+B-E)A^{-1}=2(A^{-1}+B^{-1})-(A^{-1}B^{-1}+B^{-1}A^{-1}).$$

[Хорхе]

Цитата:

Пусть минутная стрелка отклонилась на угол $2\pi\varphi$ ($\varphi\in[0;1)$). Ему соответствуют положения часовой стрелки $\psi=\frac{\pi}6(\varphi+k)\pmod{2\pi}$, $k\in\mathbb{Z}$. Наибольшая длина пересечения соответствует минимальному значению $|2\pi\varphi-\psi|=\frac{\pi}6\|11\varphi\|$ и равна $\cos\frac{\pi\|11\varphi\|}6$
Поэтому искомая площадь равна

$$\pi\int\limits_0^1\cos^2\frac{\pi\|11\varphi\|}6\,d\varphi=\pi\int\limits_0^1\cos^2\frac{\pi\|\varphi\|}6\,d\varphi=2\pi\int\limits_0^{1/2}\cos^2\frac{\pi\varphi}6\,d\varphi=\pi(1/2+3/{(2\pi)})=\frac{\pi+3}2.$$

По-любому где-нибудь наврал.

А вот и не наврал Мне, кстати, часы с таким циферблатом приснились, отсюда задача.

[RIP]

dm писал(а):

Задачи для 3--4 курсов

6. Исследовать на монотонность функцию

$$f(\sigma)=\mathsf{M}\frac{1}{1+e^\xi},\, \sigma>0,$$

где $\xi$
--- гауссовская случайная величина со средним $m$ и дисперсией
$\sigma^2,$ $m$ --- действительный параметр.

$$f(\sigma)=\frac1{\sqrt{2\pi}}\int\limits_{\mathbb{R}}\frac{e^{-x^2/2}}{1+e^{m+\sigma x}}dx=\frac1{\sqrt{2\pi}}\int\limits_0^{\infty}p(x)e^{-x^2/2}dx,$$

где

$$p(x)=\frac1{1+e^{m+\sigma x}}+\frac1{1+e^{m-\sigma x}}.$$

$p(x)$ легко исследуется на монотонность по $\sigma$.

[Юстас]

Чёрт, совсем ничего RIP с Рустом порешать не оставили

[RIP]

Юстас писал(а):

Чёрт, совсем ничего RIP с Рустом порешать не оставили

Так никто ж не заставлял читать решения

Кстати, хорошая задачка:
Существует ли многочлен $P(x)\in\mathbb{Q}[x]$ такой, что для каждого $k=1,2,\ldots,2007$ уравнение $P(x)=k$ имеет ровно $k$ рациональных корней (без учета кратностей)?

[Хорхе]

RIP писал(а):

Кстати, хорошая задачка:
Существует ли многочлен $P(x)\in\mathbb{Q}[x]$ такой, что для каждого $k=1,2,\ldots,2007$ уравнение $P(x)=k$ имеет ровно $k$ рациональных корней (без учета кратностей)?

Степени 2007, надеюсь?