Международная студенческая олимпиада, Иран 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 · **Появился:** 15/03/07 **Сообщения:** 113

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 · **Появился:** 15/03/07 **Сообщения:** 113

Численный анализ (Математика и прикладная математика).
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 · **Появился:** 08/06/07 **Сообщения:** 29

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

dm

Leader171 писал(а):

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

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

cepesh

dm писал(а):

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

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

dm

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

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

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

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

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

Leader171 · **Появился:** 08/06/07 **Сообщения:** 29

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

dm

Leader171 писал(а):

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

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

Sasha Rybak

Pyphagor писал(а):

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

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

lofar · **Появился:** 28/09/05 **Сообщения:** 258

Алгебра, на мой взгляд, вполне доступная.
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 · **Появился:** 28/09/05 **Сообщения:** 258

Индукцией по $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$ .
Ч.Т.Д. :wink:

Темы	Автор	Ответы
Олимпиада в Бобруйске по физике за 1993 год для 8-го класса в форуме Помогите решить / разобраться (Ф)	Ferd	44
Студенческая столовая в форуме Юмор, поздравления, сходки	Gravist	3
Как в ворде 2007 вставлять формулы деления в форуме Software	rosimk	8
Математическая олимпиада. 1998 год. 11 класс. #4 в форуме Помогите решить / разобраться (М)	Grappy	6
Городская олимпиада школьников за 2009 год в форуме Олимпиадные задачи (М)	Yerkhan	14

Научный форум dxdy

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

Кто сейчас на конференции

Темы с похожим названием