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

[dm]

Международная математическая олимпиада для студентов университетов
Благоевград, Болгария
3-9 августа 2007

День 1

1. Пусть $f$ - квадратный трехчлен с целыми коэффициентами. Предположим, что $f(k)$ делится на 5 для любого целого $k$. Доказать, что все коэффициенты $f$ делятся на 5.

2. Пусть $n\ge 2$ - целое число. Какие наименьший и наибольший ранги возможны у матрицы $n\times n$, чьими $n^{2}$ элементами являются в точности числа $1, 2, \ldots, n^{2}$?

3. Назовем многочлен $P(x_{1}, \ldots, x_{k})$ хорошим, если существуют такие вещественные матрицы $A_{1}, \ldots, A_{k}$ размера $2\times 2$, что
$P(x_{1}, \ldots, x_{k}) = \det \left(\sum_{i=1}^{k}x_{i}A_{i}\right).$
Найти все значения $k$, для которых все однородные многочлены степени 2 от $k$ переменных являются хорошими. (Многочлен называется однородным, если каждый член имеет одну и ту же суммарную степень.)

4. Пусть $G$ - конечная группа. Для произвольных множеств $U, V, W \subset G$ обозначим через $N_{UVW}$ количество троек $(x, y, z) \in U \times V \times W$, для которых $xyz$ является единицей. Предположим, что $G$ разбита на три множества $A$, $B$ и $C$ (т.е. множества $A, B, C$ попарно не пересекаются и $G = A \cup B \cup C$). Доказать, что $N_{ABC}= N_{CBA}.$

5. Пусть $n$ - натуральное число, а $a_{1}, \ldots, a_{n}$ - целые. Предположим, что функция $f: \mathbb{Z}\to \mathbb{R}$ удовлетворяет $\sum_{i=1}^{n}f(k+a_{i}l) = 0$ для любых целых $k$ и $l$, таких, что $l \ne 0$. Доказать, что $f = 0$.

6. Сколько ненулевых коэффициентов может быть у многочлена $P(x)$, если его коэффициенты целые и $|P(z)| \le 2$ для всех комплексных чисел $z$ единичной длины?

День 2

1. Пусть $f : \mathbb{R}\to \mathbb{R}$ - непрерывная функция. Предположим, что для любого $c > 0$ график $f$ можно передвинуть в график $cf$, используя лишь параллельные переносы и вращения. Следует ли отсюда, что $f(x) = ax+b$ для некоторых вещественных чисел $a$ и $b$?

2. Пусть $x$, $y$ и $z$ - такие целые числа, что $S = x^{4}+y^{4}+z^{4}$ делится на 29. Показать, что $S$ делится на $29^{4}$.

3. Пусть $C$ - непустое замкнутое ограниченное подмножество вещественной оси и $f: C \to C$ - неубывающая непрерывная функция. Показать, что найдется такая точка $p \in C$, что $f(p) = p$.
(Множество замкнуто, если его дополнение является объединением открытых интервалов. Функция $g$ не убывает, если $g(x) \le g(y)$ для всех $x \le y$.)

4. Пусть $n > 1$ - нечетное натуральное число и $A = (a_{ij})_{i, j = 1\ldots n}$ - матрица $n \times n$ с элементами

\[ a_{ij}= \begin{cases}2, & \text{если }i = j \\ 1, & \text{если }i-j \equiv \pm 2 \pmod n \\ 0 & \text{в остальных случаях.}\end{cases} \]

Найти $\det A$.

5. Для каждого натурального $k$ найти наименьшее число $n_{k}$, для которого существуют такие вещественные матрицы $A_{1}, A_{2}, \ldots, A_{k}$ размера $n_{k}\times n_{k}$, что выполнены все следующие условия:
(1) $A_{1}^{2}= A_{2}^{2}= \ldots = A_{k}^{2}= 0$,
(2) $A_{i}A_{j}= A_{j}A_{i}$ для всех $1 \le i, j \le k$
и
(3) $A_{1}A_{2}\ldots A_{k}\ne 0$.

6. Пусть $f \ne 0$ - многочлен с вещественными коэффициентами. Определим последовательность $f_{0}, f_{1}, f_{2}, \ldots$ многочленов: $f_{0}= f$ и $f_{n+1}= f_{n}+f_{n}'$ для всех $n \ge 0$. Доказать, что найдется такое число $N$, что для всех $n \ge N$ все корни $f_{n}$ вещественны.

http://www.imc-math.org.uk/
http://www.mathlinks.ro/Forum/index.php?f=79

Результаты (индивидуальный зачет) приаттачил здесь: http://www.mathlinks.ro/Forum/viewtopic ... 541#907541

Топ командного зачета (один из вариантов - лучшие три результата в команде плюс среднее остальных):
1 - Будапештский университет
2 - МГУ
3 - Шарифский технологический университет (Иран)
4 - Принстонский университет
5 - Варшавский университет
6 - Киевский национальный университет им. Т.Шевченко

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

Результаты команды Московского университета:
No Name University 1 2 3 4 5 6 S1 1 2 3 4 5 6 S2 S1+S2 Prize
1 Alexander Efimov Moscow State University 20 20 20 20 20 20 120 20 20 20 20 20 3 103 223 Grand First
8 Vasily Astakhov Moscow State University 20 20 20 20 0 15 95 20 20 18 12 20 2 92 187 First Prize
12 Dmitry Baranov Moscow State University 18 20 20 20 15 1 94 20 20 20 0 20 0 80 174 First Prize
13 Aleksandr Perepechko Moscow State University 20 20 18 20 0 1 79 20 16 20 18 20 0 94 173 First Prize
30-31 Sergey Smirnov Moscow State University 20 20 0 20 0 1 61 20 17 20 0 20 2 79 140 First Prize

Результаты команды Киевского университета:
No Name University 1 2 3 4 5 6 S1 1 2 3 4 5 6 S2 S1+S2 Prize
22-23 Ivan Feschenko Kyiv Taras Shevchenko University 20 18 18 18 10 7 91 20 19 20 0 0 2 61 152 First Prize
25-26 Iaroslav Zhurba Kyiv Taras Shevchenko University 20 19 20 0 0 0 59 20 20 20 3 20 0 83 142 First Prize
27-29 Oleksandr Kravets Kyiv Taras Shevchenko University 20 20 20 0 1 0 61 20 20 20 0 20 0 80 141 First Prize
32-33 Ivan Iurchenko Kyiv Taras Shevchenko University 20 17 20 20 0 0 77 20 20 20 0 0 2 62 139 First Prize
38-39 Sergii Slobodianiuk Kyiv Taras Shevchenko University 20 10 10 15 0 0 55 20 20 20 17 0 0 77 132 First Prize
60 Larisa Homenko Kyiv Taras Shevchenko University 20 20 20 0 0 2 62 0 17 20 10 0 0 47 109 Second Prize
79-80 Ivan Livinskii Kyiv Taras Shevchenko University 20 15 4 0 0 0 39 20 20 20 0 0 1 61 100 Second Prize
118-121 Taras Tymoshkevych Kyiv Taras Shevchenko University 20 20 0 1 0 0 41 0 0 20 20 0 1 41 82 Third Prize

[neo66]

dm писал(а):

2. Пусть $n\ge 2$ - целое число. Какие наименьший и наибольший ранги возможны у матрицы $n\times n$, чьими $n^{2}$ элементами являются в точности числа $1, 2, \ldots, n^{2}$?

Похоже, что $2$ и $n$.

[neo66]

dm писал(а):

3. Пусть $C$ - непустое замкнутое ограниченное подмножество вещественной оси и $f: C \to C$ - неубывающая непрерывная функция. Показать, что найдется такая точка $p \in C$, что $f(p) = p$.

Возьмем произвольную точку $p_1 \in C$. Расссмотрим последовательность $p_1,p_2 \dots, p_{n+1} = f(p_n), \dots$. Поскольку она неубывает и ограниченна, а $C$ - замкнуто, то $\exists$ $\lim\limits_{n \to \infty} p_n = p \in C$. Пользуясь непрерывностью $f$, легко показать, что эта точка $p$ - неподвижная точка нашей функции.

[dm]

neo66 писал(а):

Расссмотрим последовательность $p_1,p_2 \dots, p_{n+1} = f(p_n), \dots$. Поскольку она неубывает ...

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

[dewgong]

День 2
4. Этот опр-ль яв-ется циркулянтом =$\displaystyle\prod_{k=1}^{2m+1}(2+\epsilon_k + \epsilon_{2m+1-k})=\displaystyle\prod_{k=1}^{2m+1} (2 \cos {\frac{2\pi k}{2m+1}})^2=4$ хотя я использывал тригонометрическое тождество которое не могу доказать.... $n=2m+1$

[neo66]

dm писал(а):

neo66 писал(а):

Расссмотрим последовательность $p_1,p_2 \dots, p_{n+1} = f(p_n), \dots$. Поскольку она неубывает ...

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

Верно. И поделом .

[Macavity]

Первые задачи обоих дней вроде не сложные. Во всяком случае...

dm писал(а):

Международная математическая олимпиада для студентов университетов
Благоевград, Болгария
3-9 августа 2007

День 1

1. Пусть $f$ - квадратный трехчлен с целыми коэффициентами. Предположим, что $f(k)$ делится на 5 для любого целого $k$. Доказать, что все коэффициенты $f$ делятся на 5.
....

F(x)=ax^2+bx+c=0$ (mod 5)$ если x \in \mathbb{Z}$, a \in \mathbb{Z}$, b \in \mathbb{Z}$, c \in \mathbb{Z}$

Если x=0 \Rightarrow c=0$ (mod 5)$
а если подставить x=1, а затем x=-1, то получим b=0$ (mod 5)$ и a=0$ (mod 5)$

dm писал(а):

День 2

1. Пусть $f : \mathbb{R}\to \mathbb{R}$ - непрерывная функция. Предположим, что для любого $c > 0$ график $f$ можно передвинуть в график $cf$, используя лишь параллельные переносы и вращения. Следует ли отсюда, что $f(x) = ax+b$ для некоторых вещественных чисел $a$ и $b$?
....

Ответ - не следует.

Контрпример f(x)=e^x

Тогда если c>0 \Rightarrow cf(x)=ce^x=e^{c_1}e^x=e^{c_1+x}=f(x+c_1)
совпадение графиков получается движением графика вдоль оси X.

[dm]

Macavity писал(а):

Ответ - не следует.

Контрпример f(x)=e^x

Более сложный вариант задачи - описать все такие функции.

[Macavity]

dm писал(а):

Более сложный вариант задачи - описать все такие функции.

Ха. Это уже думать надо.

[Macavity]

dm писал(а):

День 2

1. Пусть $f : \mathbb{R}\to \mathbb{R}$ - непрерывная функция. Предположим, что для любого $c > 0$ график $f$ можно передвинуть в график $cf$, используя лишь параллельные переносы и вращения. Следует ли отсюда, что $f(x) = ax+b$ для некоторых вещественных чисел $a$ и $b$?
....

dm писал(а):

Macavity писал(а):

Ответ - не следует.

Контрпример f(x)=e^x

Более сложный вариант задачи - описать все такие функции.

Macavity писал(а):

Ха

рошо.. Попробую.

Во-первых, рассмотрим cf, если с>0, то это преобразование является растяжением (или растяжением-сжатием) вдоль оси y, обозначим его U(c,f) и обратим внимание на то, что такие преобразования образуют коммутативную мультипликативную группу.
U(1,...) - это единица группы
{U(с_1,f)}{*}{U(c_2,f)}=U(c_1c_2,f) - выражение для групповой операции
U^{-1}(c,f)=U(\frac {1} {c},f) - обратный элемент.

Что же касается преобразований, которые выражаются через параллельные переносы и вращения, то они в двумерном евклидовом пространстве образуют группу собственных движений: x=Az+v, здесь A это ортогональная матрица с определителем 1 (что и определяет собственные движения плоскости), а v - вектор сдвига. Таким образом, интересуют такие функции f, для которых трансформация группы растяжения вдоль оси y, действует, как некоторое собственное движение плоскости.

Известна следующая
Лемма. Любое собственное движение плоскости есть вращение вокруг некоторой точки или сдвиг.
Доказательство. Пусть движени имеет вид x=Az+v, или z \to Az+v, где A = \left ( \begin {array}{cc} \cos \varphi & \sin \varphi \\ -\sin \varphi & \cos \varphi \end {array} \right)
Если \varphi=0, то A - единичная матрица и получается чистый сдвиг.
Пусть теперь A - не является единичной матрицей. Найдем центр вращения движения. Центр вращения должен быть неподвижной точкой преобразования и это значит, что
для него (z_0) верно равенство z_0=Az_0+v. И далее (1-A)z_0=v. Так как (см. выше) матрица A не является единичной, то det(1-A) \neq 0 и уравнение всегда имеет решение (центр вращения выражается однозначно).
Ч.т.д.

Итак у собственного движения может быть одна (вращение) или не одной (сдвиг) неподвижной точки (в крайнем случае возможен вырожденный вариант: все точки неподвижны - единица группы собственных движений плоскости). И есть два типа собственных движений - сдвиг и вращение, значит имеет смысл искать два типа функций, каждый из которых отвечает своему типу собственных движений (хотя это не обязательно имеет место).
Вернёмся к растяжениям вдоль оси y. Что для этой трансформации неподвижные точка? Очевидно, это нули функции f. Они и остаются нулями после преобразования U, независимо от значения c.Вывод такой: сразу из области поиска можно выбросить те функции, которые имеют конечное количество нулей (>1). Все эти многочлены высоких степеней можно не рассматривать...

Рассмотрим вращения (те функции, трансформации которых приводят к вращениям). Во-первых, центр вращения из отмеченного выше всегда лежит на оси x. С другой стороны, так как c \neq 0, то никакая из точек графика функции не окажется при вращении на оси x, но может как угодно близко приближаться к оси x, так как c может быть как угодно близок к нулю. И отсюда, после некоторыхсоображений, следует вывод, что данная функция не может ни на каких участках быть вогнутой или выпуклой. То есть, эта функция всегда прямая, которая обязательно (центр вращения) пересекает ось x. То есть для движений типа вращение функция имеет вид $f(x) = ax+b$.

Для движений типа сдвигов, как было показано выше у собственного движения не должно быть ни одной неподвижной точки. Это означает, что весь график находится или над осью x, или под ней, либо это сама ось x (преобразование U переводит такую функцию всегда в себя).
Поскольку преобразование является сдвигом, если это чистый сдвиг по вертикали, то решением является функция y=const. Если это сдвиги по горизонтали и тогда можно записать: сf(x)=f(x+t)
Этому функциональному уравнению соответствут показательная функция (затрудняюсь сказать как можно доказать, что других типов функций нет):
Вероятно так
f(x)=\pmСe^{fx+g} и плюс вырожденный случай, прямая y=0.

[Sasha Rybak]

Macavity писал(а):

Вероятно так
$f(x)=\pm e^{fx+g}$ и плюс вырожденный случай, прямая $y=0$.

Тогда уже $f(x)=\pm e^{ax+b}+c$ и $y=c$. Или попросту $f(x)=be^{ax}+c$.
К тому же, $f(x)=\pm e^{fx+g}$ - это уже функциональное уравнение. :)

[juna]

dm писал(а):

2. Пусть $x$, $y$ и $z$ - такие целые числа, что $S = x^{4}+y^{4}+z^{4}$ делится на 29. Показать, что $S$ делится на $29^{4}$.

Вроде, кроме $x\equiv y\equiv z\equiv 0 \mod 29$, решений сравнения $x^4+y^4+z^4\equiv 0 \mod 29$ нет.

[Macavity]

Sasha Rybak писал(а):

Тогда уже $f(x)=\pm e^{ax+b}+c$ и $y=c$. Или попросту $f(x)=be^{ax}+c$.

Да, Саша, в конце я подзапутался. У тебя правильнее и красивше,...
но всё же мне кажется, что правильнее так:
$f(x)=be^{ax}+c$ и дополнительное условие bc\geqslant 0. Иначе, f(x) будет иметь 0 (а это неподвижная точка для U). Или нет?

Sasha Rybak писал(а):

К тому же, $f(x)=\pm e^{fx+g}$ - это уже функциональное уравнение.

[Sasha Rybak]

Macavity писал(а):

но всё же мне кажется, что правильнее так:
$f(x)=be^{ax}+c$ и дополнительное условие bc\geqslant 0. Иначе, f(x) будет иметь 0 (а это неподвижная точка для U). Или нет?

Условия не нужны. Если f(x) имеет указанное свойство, то и f(x)+c его имеет. Действительно, пусть графики y=f(x) и y=kf(x) совместимы движением. Тогда и графики y=f(x)+c и y=kf(x)+kc совместимы движением, поскольку первый - это
сдвиг графика y=f(x) а второй - сдвиг графика y=kf(x).