Международная студенческая олимпиада, Иран 2007

[dm]

12-я Международная научная олимпиада по математике для студентов университетов
10–13 июля 2007
Тегеран, Иран

I. Математический анализ (математика и прикладная математика)

1. (25 баллов) Предположим, что функция $f:\mathbb{R}^n\to\mathbb{R}^n$ удовлетворяет следующим двум условиям:
i) $f(K)$ компактно для любого компактного множества $K$ в $\mathbb{R}^n$;
ii) $f\left(\bigcap_{n=1}^{\infty}K_n\right)=\bigcap_{n=1}^{\infty}f(K_n)$ для любой убывающей последовательности $\{K_n\}_{n=1}^{\infty}$ компактных множеств в $\mathbb{R}^n$.
Доказать, что $f$ непрерывна.

2. (25 баллов) Предположим, что $f$ — вещественнозначная дважды дифференцируемая функция, определенная на $[a,b]$. Показать, что существуют $\xi$, $\eta$ в $[a,b]$, такие, что

$$f(\eta)-f(a)\frac{b-\eta}{b-a}-f(b)\frac{\eta-a}{b-a}-\frac{1}{2}(\eta-a)(\eta-b)f''(\xi)=0.$$

3. (25 баллов) Пусть $f_n:\mathbb{R}\to\mathbb{R}$ — последовательность функций со следующими свойствами:
i) каждая $f_n$ ($n=1,2,\ldots$) — периодическая функция с периодом $T$;
ii) каждая $f_n$ ($n=1,2,\ldots$) непрерывна на $\mathbb{R}$;
iii) последовательность $\{f_n\}_{n=1}^{\infty}$ равномерно ограничена на $\mathbb{R}$.
Тогда $\{f_n\}_{n=1}^{\infty}$ — равностепенно непрерывная последовательность функций на $[0,T]$.
Доказать или опровергнуть это утверждение.

4. (25 баллов) Предположим, что $f:[0,\infty)\to\mathbb{R}$ непрерывна и $\lim_{x\to\infty}f(x)=L$. Показать, что для каждого $a>0$

$$\lim_{n\to+\infty}\int_0^af(nx)\,\mathrm{d}x=aL.$$

II. Численный анализ (математика и прикладная математика)

1. (25 баллов) Пусть $g$ — функция, определенная на $[a,b]$, со свойствами:
i) если $x\in[a,b]$, то $g(x)\in[a,b]$;
ii) $g'$ непрерывна на $[a,b]$;
iii) для всех $x\in[a,b]$: $\lvert g'(x)\rvert<1$.
1) Доказать, что уравнение $x=g(x)$ имеет ровно один корень на $[a,b]$.
2) Показать, что если условие i) не выполнено, то уравнение $x=g(x)$ может не иметь корней на $[a,b]$.

2. (25 баллов) Пусть $f$ непрерывна на $[a,b]$, $h=\frac{b-a}{n+1}$ и $x_{i+1}-x_i=h$, $i=0,1,\ldots,n$, $a=x_0<x_1<\ldots<x_n<x_{n+1}=b$.
1) Найти весовые коэффициенты в квадратурных формулах Ньютона-Котеса открытого типа:

$$\int_a^bf(x)\,\mathrm{d}x\approx\sum_{i=1}^nw_if(x_i).$$

2) Найти трехточечную квадратурную формулу Ньютона-Котеса открытого типа для $\int_0^{4h}f(x)\mathrm{d}x$.
3) Почему квадратурные формулы Ньютона-Котеса открытого типа обычно не используются?

3. (25 баллов) Пусть $\alpha$ — фиксированное положительное вещественное число; определим

$$x_{n+1}=\frac{x_n^3+3\alpha x_n}{3x_n^2+\alpha},\quad n=0,1,\ldots$$

Предположим, что $x_0$ таково, что последовательность $\{x_n\}$ сходится.
1) Найти $\lim_{n\to\infty}x_n$.
2) Определить скорость сходимости последовательности $\{x_n\}$.

4. (25 баллов) Найти коэффициенты $a$, $b$, $c$, $d$, $m$, $n$ и $p$, при которых для дифференциального уравнения $y'=f(x,y)$ формулы Рунге-Кутта
\begin{align*} &k_1=hf(x,y),\quad k_2=hf(x+mh,y+mk_1),\\ &k_3=hf(x+nh,y+nk_2),\\ &k_4=hf(x+ph,y+pk_3),\\ &y(x+h)-y(x)\approx ak_1+bk_2+ck_3+dk_4 \end{align*}
соответствуют разложению Тейлора порядка $h^4$.

III. Алгебра (математика)

1. (25 баллов) Пусть $R$ — кольцо с единицей.
Доказать, что:
1) Если каждый обратимый элемент централен, то каждый нильпотентный элемент централен.
2) Если каждый нильпотентный элемент централен, то каждый идемпотентный элемент централен.

2. (25 баллов) Пусть $G$ — нециклическая группа порядка $p^n$, где $p$ — простое число. Доказать, что у $G$ не менее $p+3$ подгрупп.

3. (25 баллов) Пусть $G$ — конечная группа ровно с 50-тью силовскими 7-подгруппами. Пусть $P\in Syl_7(G)$ и $N=N_G(P)$.
1) Доказать, что $N$ — максимальная подгруппа $G$.
2) Если у $N$ есть силовская 5-подгруппа $Q$ и $Q\lhd N$, то доказать, что $Q\lhd G$.

4. (25 баллов) Пусть $R$ — такое кольцо, что из $x^3=0$ следует, что $x=0$. Пусть для всех $a,b\in\mathbb{R}$: $(ab)^2=a^2b^2$. Доказать, что $R$ коммутативно.

Исследование операций (прикладная математика)

1. (25 баллов) Матрица $A$ размера $m\times n$, $m\le n$, с целыми элементами называется вполне унимодулярной, если каждая подматрица $B$, составленная из набора $m$ различных столбцов $A$, такова, что $\lvert\det(B)\rvert=1$ (любая такая $B$ также называется унимодулярной).

1) Доказать, что если целочисленная матрица $B$ размера $m\times m$ унимодулярна, то $B^{-1}$ также унимодулярна (и целочисленна).

2) Рассмотрим задачу линейного программирования:
\begin{gather*} z=c^Tx\to\min,\\ Ax=b,\tag{LP}\\ x\ge0, \end{gather*}
где $A$ — целочисленная матрица размера $m\times n$, $m\le n$, и $b$ — целочисленный вектор. Доказать, что если $A$ вполне унимодулярна и у (LP) есть оптимальное решение, то симплекс-метод для задачи (LP) найдет оптимальное целочисленное решение (в предположении, что (LP) невырожденна).

2. (25 баллов) Рассмотрим задачу линейного программирования:
\begin{gather*} q^Tx\to\min,\\ Mx\ge-q,\tag{LP}\\ \quad x\ge0, \end{gather*}
где $M=-M^T$ и $q$ заданы. Доказать, что:
1) $x\ge0$ — оптимальное решение (LP) тогда и только тогда, когда выполнено:

$$s(x)=Mx+q\ge0,\quad x^Ts(x)=0.$$

2) Две допустимые точки $x$ и $y$ для (LP) являются ее оптимальными точками тогда и только тогда, когда выполнено:

$$x_is_i(y)=y_is_i(x),\quad i=1,\ldots,n.$$

3) Если $q\ge0$, то у задачи (LP) есть оптимальное решение.

3. (25 баллов) Доказать 1) и 2), используя элементарные определения выпуклых множеств и выпуклых функций.
1) Показать, что множество

$$S=\{x\in\mathbb{R}^n\mid Ax=b,\ x\ge0\}$$

выпукло.
2) Показать, что если $x^*$ — оптимальное (локальное) решение задачи
\begin{gather*} z=c^Tx\to\min,\\ Ax=b,\tag{LP}\\ x\ge0, \end{gather*}
то $x^*$ — глобальное решение.
Доказать или опровергнуть 3) и 4).
3) Задача (LP) может быть недопустимой.
4) Задача (LP) может быть неограниченной.

4. (25 баллов) Предположим, что $S$ — непустое открытое выпуклое множество в $\mathbb{R}^n$ и $f:S\to\mathbb{R}$ дифференцируема на $S$. Доказать, что если $f$ выпукла на $S$, то выполнено:

$$\bigl(\nabla f(x_2)-\nabla f(x_1)\bigr)^T(x_2-x_1)\ge0\quad\text{для всех $x_1,x_2\in S$}.$$

IV. Линейная алгебра (математика и прикладная математика)

1. (33.3 балла) Пусть $A\in M_n(\mathbb{C})$ и $\mathbb{C}[A]=\{f(A)\mid f(x)\in\mathbb{C}[x]\}$. Доказать, что у кольца $\mathbb{C}[A]$ нет ненулевых нильпотентных элементов тогда и только тогда, когда $A$ диагонализируема.

2. (33.3 балла) Доказать, что если $n$ — натуральное число, то существует такая обратимая матрица $A=(a_{ij})$ размера $2\times2$, что $a_{ij}\in\mathbb{R}$, $A^n=I$ и $A^k\ne I$ для всех $1\le k<n$.

3. (33.3 балла) Пусть $X$ — обратимая матрица со столбцами $X_1,X_2,\ldots,X_n$. Пусть $Y$ — матрица со столбцами $X_2,X_3,\ldots,X_n,0$. Показать, что у матриц $A=YX^{-1}$ и $B=X^{-1}Y$ ранг $n-1$, а их собственные числа — только нули.

Оригиналы условий на английском: http://www.mathlinks.ro/Forum/viewtopic.php?t=158736

Результаты: http://olympiad.sanjesh.org/EnglishV/Ne ... 31124.aspx

[Pyphagor]

4. Линейная Алгебра.
2. Достаточно взять $A = (a_i_j)$,
$a_{1}_{1} = a_{2}_{2} = cosz, a_{1}_{2} = -a_{2}_{1} = -sinz $
$ z = \frac{2\pi} {n} $.

P.S. Сразу чувствуется уровень.

[Pyphagor]

Численный анализ (Математика и прикладная математика).
3a.Отметим, что если и существует предел, то он может быть равен только $0$,$\sqrt{a}$,
$-\sqrt{a}$.
Введем
$ f(z) = \frac{z^3+3az}{3z^2+a} $, $ A = f(z) - z = \frac{2z(a-z^2)}{3z^2+a} $.
Рассмотрим случаи: $ x_{0} < -\sqrt{a}, -\sqrt{a} < x_{0} < 0, 0<x_{0}<\sqrt{a}, x_{0}>\sqrt{a}. $
Имеем $ f'(z) = \frac{3(z^2-a)^2}{(3z^2+a)^2} > 0 $. Т.е. $f(z)$ - возрастающая на всей числовой прямой.
В первом случае если $x_n < -\sqrt{a}$ , то $x_{n+1} = f(x_n) < f(-\sqrt{a}) = -\sqrt{a} $, при этом $A > 0$, т.е.
последовательность $x_n$ - возрастающая, и предел равен $-\sqrt{a}$.
Повторяя аналогичные
рассуждения и рассматривая тривиальные случаи $x_{0} = 0, -\sqrt{a}, \sqrt{a},$
заключаем, что $\lim\limits_{n \to \infty} x_n$ = $sign(x_0)*\sqrt{a}$.

P.S. Что такое скорость сходимости последовательности?
Скажем, чему равна эта величина для $x_n$ = $\frac{1}{n}$ ?

[dm]

Pyphagor писал(а):

Что такое скорость сходимости последовательности?

То, на что надо домножить разность последовательности и предела, чтобы предел был конечен (не ноль и не бесконечность). Иными словами, спрашивается следующий член асимптотики.

[Leader171]

Говорят, там наши второе место заняли... А кто первое?

[dm]

Leader171 писал(а):

Говорят, там наши второе место заняли... А кто первое?

Естественно, хозяева - иранцы. За нами третьи - китайцы. Это всё в командном зачете. Индивидуальный можно посмотреть здесь:
http://olympiad.sanjesh.org/EnglishV/Ne ... 31124.aspx
У нас одно золото, два серебра и две бронзы. Так что все с призами.
Наше золото (Саша Рыбак) - это лучший результат по сумме баллов за все время, что Украина ездит в Иран.

[cepesh]

dm писал(а):

за все время, что Украина ездит в Иран

А что, Украина часто ездит в Иран?

[dm]

cepesh
Да, вроде каждый год, как не лень.

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

В этом году это была 12-я олимпиада в Иране.
Украина ездила в 5-й раз (были пропуски).

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

Россия ездила, кажется, один раз.
В Иране все оплачивается за счет принимающей стороны, кроме дороги. Россия поставила условие, чтобы команде и дорогу тоже оплатили. Иранцы один раз оплатили, а на следующий раз отказались.

[Leader171]

Что, каждый год в Иране проходит?

[dm]

Leader171 писал(а):

Что, каждый год в Иране проходит?

Именно эта олимпиада - да.

[Sasha Rybak]

Pyphagor писал(а):

P.S. Сразу чувствуется уровень.

А ты алгебру попробуй решить. :)

[lofar]

Алгебра, на мой взгляд, вполне доступная.
1. Если $a$ --- нильпотент, то $1+a$ --- обратим. Если $f$ --- идемпотент, то $fr(1-f)$ --- нильпотент.

2. У группы $H_{p^2}=\mathbb Z_p\oplus\mathbb Z_p$ ровно $p+3$ подгруппы. В $G$ существуют подгруппы $A$ и $B$ такие, что $A\lhd B$ и $B/A\cong H_{p^2}$.

[Sasha Rybak]

lofar писал(а):

2. У группы $H_{p^2}=\mathbb Z_p\oplus\mathbb Z_p$ ровно $p+3$ подгруппы. В $G$ существуют подгруппы $A$ и $B$ такие, что $A\lhd B$ и $B/A\cong H_{p^2}$.

У этой задачи есть намного более простое решение. А именно - рассмотреть все циклические подгруппы, кроме {e}. Их не менее p+1, иначе их объединение не покроет группу. Отдельно рассмотрим {e} и всю группу.

Это, как раз, была самая простая задача в туре (по-моему). А насчёт "доступности" - надо учитывать, что на всё удовольствие было дано 2 часа. :)

К слову, можешь написать доказательство существования указанных подгрупп A, B? А то простого решения этого для факта я не нашёл.

[lofar]

Индукцией по $n$ докажем, что у всякой нециклической группы $G$ порядка $p^n$ имеется фактор ($B/A$ в обозначениях предыдущего поста) изоморфный $H_{p^2}$.

$n=2$. Тогда $G\cong H_{p^2}$.

$n>2$. В центре $G$ существует подгруппа $C$ порядка $p$. Если $G/C$ циклическая, то $G$ --- абелева и в ней есть подгруппа (а значит и фактор) изоморфная $H_{p^2}$. Если $G/C$ не циклическая, то по индукции в $G/C$ найдутся подгруппы $\overline B$ и $\overline A$ такие, что $\overline A\lhd\overline B$ и $\overline A/\overline B\cong H_{p^2}$. В качестве искомых подгрупп $A$ и $B$ в $G$ берем прообразы относительно канонического эпиморфизма $G\to G/C$ подгрупп $\overline A$ и $\overline B$ соответственно.

[Хет Зиф]

Алгебра.
4. $x^2=0\Rightarrow x^2 x =x^3=0\Rightarrow x=0 $ .Таким образом $x^2=0 \Leftrightarrow x=0$
Пусть: $ ab=0 \Rightarrow b(ab)a=0 \Rightarrow (ba)^2=0 \Rightarrow ba=0 $
Далее: $a\neq 0, b\neq 0 ,ab\neq 0$, тогда
$(ab)^2-aabb=0 \Rightarrow a(ba-ab)b=0 \Rightarrow (ab-ba)ba=0 \Rightarrow abba-(ba)^2=0 $
Также: $(ba)^2=bbaa\Rightarrow b(ab-ba)a=0 \Rightarrow (ab-ba)ab=0 \Rightarrow (ab)^2-baab =0$
И так:
$(ab-ba)^2=(ab)^2 -abba -baab +(ba)^2 =((ab)^2-baab)+((ba)^2-abba)=0+0=0\Rightarrow ab-ba=0 \Rightarrow ab=ba$.
Ч.Т.Д.