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

[dm]

Kyiv Taras Shevchenko University Mechmat Competition
6 March 2013


Problems for 1st and 2nd year students

1. Find all such continuous functions $f:[1,2]\to[1,2]$ that $f(1)=2$ and $f(f(x))f(x)=2$ for all $x\in[1,2]$. (Ivan Feshchenko)

2. Does there exist such a finite ring (not necessarily commutative or with a unit) that for every its element $x$ there exists such an element $y$ different from $x$ that $y^2=x\,?$ (Sergiy Slobodianiuk)

3. In a given triangle the lengths of sides and tangents of angles are arithmetic progressions. Find the angles. (Alexander Kukush, Maria Rozhkova)

4. Let $x_1,\ldots,x_n,c>0$. Prove the inequality

$$\[\sqrt{{x_1+\sqrt{{x_2+\sqrt{{\ldots+\sqrt{x_n+c}}}}}}}<\sqrt{{x_1+\sqrt{{x_2+\sqrt{{\ldots+\sqrt{x_n}}}}}}}+\dfrac{c}{2^n\,\sqrt{{x_1\ldots x_n}}}\,\,.\]$$

(Ivan Feshchenko)

5. Let $A,B$ be such $n\times n$ matrices that for every $n\times n$ matrix $C$ the equation $AX+YB=C$ has a solution $X, Y$. Prove that then for every matrix $C$ the equation $A^{2013}X+YB^{2013}=C$ has a solution too. (Ivan Feshchenko)

6. There are given such functions $f,g: {\mathbb R} \to {\mathbb R}$ that for every two different numbers $x,y$ either the inequality $f(x) + g(y) > 0$ or inequality $f(y) + g(x) > 0$ holds. Prove that there do not exist such numbers $a$ and $b$ that for all $x\in(a,b)$ the inequality $f(x) + g(x) < 0$ holds. (Oleksiy Rudenko)

7. A positive integer is called good if it is the $k$-th power of an integer for some $k\ge 2$. Is finite or infinite the set of all integers that are not sums of two good integers? (Andriy Bondarenko)

8. Let $A=\left(\begin{matrix} 1 & 2\\ 0 & 1 \end{matrix}\right)\!,$ $B=\left(\begin{matrix} 1 & 0\\ -2 & 1 \end{matrix}\right)$. Can a product $X_1X_2\ldots X_n$ equal the unit matrix if every multiplier $X_i$ equals either $A$ or $B\,?$ (Yevgen Makedonsky)


Problems for 3rd-5th year students

1. Calculate the sum of series

$$\[\sum_{n=0}^{\infty}\frac{1}{n!\,2^n}\cos\frac{\pi n-1}{2}.\]$$

(Dmytro Mitin)

2. Does there exist such a finite nonzero ring (not necessarily commutative or with a unit) that for every nonzero element $x$ there exists such an element $y$ different from $x$ that $y^2=x\,?$ (Sergiy Slobodianiuk)

3. There are given such functions $f,g: {\mathbb R} \to {\mathbb R}$ that for every two different numbers $x,y$ either the inequality $f(x) + g(y) > 0$ or inequality $f(y) + g(x) > 0$ holds. Prove that there do not exist such numbers $a$ and $b$ that for all $x\in(a,b)$ the inequality $f(x) + g(x) < 0$ holds. (Oleksiy Rudenko)

4. Let $A,B$ be such $n\times n$ complex matrices that for every $n\times n$ matrix $C$ the equation $AX+YB=C$ has a solution $X, Y$. Prove that $k_0(A)+k_0(B)\le n\,,$ where $k_0(U)$ is the number of zeroes in the main diagonal of Jordan form of $U$. (Ivan Feshchenko)

5. Let $f:\mathbb{R}^{2}\rightarrow\mathbb{R}.$ Is it always true that

$$\[\text{ess\,sup}_{x\in\mathbb{R}}\bigl(\text{ess\,sup}_{y\in\mathbb{R}}f(x,y)\bigr)=\text{ess\,sup}_{y\in\mathbb{R}}\bigl(\text{ess\,sup}_{x\in\mathbb{R}}f(x,y)\bigr)\,?\]$$

(Here the essential supremums are taken with respect to Lebesgue measure on the line). (Alexander Kukush)

6. Do there exist such real nonconstant rational functions $\varphi(x)$ and $\psi(x)$ that $\psi'(x)=\dfrac{\varphi'(x)}{\varphi(x)}$ for all $x$ from the intersection of definition domains for left and right hand sides of the equality? (Yevgen Makedonsky)

7. Let $\mathsf{P}$ be such a probabilistic measure on Borel $\sigma$-algebra on $\mathbb{R}^2$ that for every straight line $\ell$ it is true that $\mathsf{P}(\ell)<1.$ Does there always exist such a bounded Borel set $A$ that for every straight line $\ell$ it is true that $\mathsf{P}(A\cap\ell)<\mathsf{P}(A)\,?$ (Alexander Kukush)

8. Let $\{a_n\}$ be such a sequence of real numbers that $\sum\limits_{n=1}^{\infty}a_n^2<\infty,$ $\{\xi_n\}$ be a sequence of independent identically distributed random variables with distribution $\mathsf{P}\{\xi_1=1\}=2/3,\,\mathsf{P}\{\xi_1=0\}=1/3$ and $S_n=\sum\limits_{k=1}^n\xi_k.$ Prove that the series $\sum\limits_{n=1}^{\infty}(-1)^{S_n}a_n$ converges in probability. (Georgiy Shevchenko)


Time allowed: 3 hours

[EtCetera]

dm в сообщении #693504 писал(а):

1. Calculate the sum of series

$$\[\sum_{n=0}^{\infty}\frac{1}{n!\,2^n}\cos\frac{\pi n-1}{2}.\]$$

(Dmytro Mitin)

$$\sum_{n=0}^{\infty}\frac{1}{n!\,2^n}\cos\frac{\pi n-1}{2}=\operatorname{Re}\sum_{n=0}^{\infty}\frac{e^{i\frac{\pi n-1}{2}}}{n!\,2^n}=\operatorname{Re} e^{-\frac{i}{2}}\sum_{n=0}^{\infty}\frac{\left(\frac{e^{i\frac{\pi}{2}}}{2}\right)^n}{n!}=\operatorname{Re} e^{-\frac{i}{2}}\sum_{n=0}^{\infty}\frac{\left(\frac{i}{2}\right)^n}{n!}=\operatorname{Re} e^{-\frac{i}{2}}e^{\frac{i}{2}}=1$$

[ewert]

dm в сообщении #693504 писал(а):

. Do there exist such real nonconstant rational functions $\varphi(x)$ and $\psi(x)$ that $\psi'(x)=\dfrac{\varphi'(x)}{\varphi(x)}$

Является ли логарифм рациональной функцией?

[nnosipov]

ewert в сообщении #693530 писал(а):

Является ли логарифм рациональной функцией?

Вполне содержательный алгебраический вопрос.

[TOTAL]

dm в сообщении #693504 писал(а):

1. Calculate the sum of series

$$\[\sum_{n=0}^{\infty}\frac{1}{n!\,2^n}\cos\frac{\pi n-1}{2}.\]$$

(Dmytro Mitin)

$$\cos\left(\frac{x}{2} - \frac{1}{2} \right)= \sum_{n=0}^{\infty}\frac{x^n}{n!}\left(\frac{d^n}{dx^n}\cos\left(\frac{x}{2} - \frac{1}{2} \right)\right)_{x=0}=\sum_{n=0}^{\infty}\frac{x^n}{n!\,2^n}\cos\frac{\pi n-1}{2}.$$

[ewert]

nnosipov в сообщении #693544 писал(а):

Вполне содержательный алгебраический вопрос.

Но не для олимпиады же. Т.е. не на олимпиаде же его разбирать.

[xmaister]

nnosipov в сообщении #693544 писал(а):

Является ли логарифм рациональной функцией?

Так является или нет?

[ewert]

xmaister в сообщении #693621 писал(а):

Так является или нет?

Очевидно, нет. А почему очевидно -- вопрос совсем не олимпиадный. Например, потому, что ТФКП и точки ветвления. Но сам факт всем и безо всякой теории известен чуть ли не с младенчества.

Это примерно то же, что предлагать на олимпиаде доказать непрерывность или дифференцируемость логарифма. Все про это прекрасно знают, но очень мало кому это когда-либо строго доказывалось.

Хотя смутно можно догадаться, что имели в виду сочинители. Скорее всего, что справа все полюса простые, а слева -- кратные. И тогда никакой ТФКП не нужно даже формально; однако с логарифмом всё равно всё очевиднее.

[Sonic86]

dm в сообщении #693504 писал(а):

8. Let $A=\left(\begin{matrix} 1 & 2\\ 0 & 1 \end{matrix}\right)\!,$ $B=\left(\begin{matrix} 1 & 0\\ -2 & 1 \end{matrix}\right)$. Can a product $X_1X_2\ldots X_n$ equal the unit matrix if every multiplier $X_i$ equals either $A$ or $B\,?$ (Yevgen Makedonsky)

Нет, порождаемая группа - это свободная группа $F_2$. Доказательство есть в Каргаполове Мерзлякове Теория групп.

[nnosipov]

ewert в сообщении #693630 писал(а):

Скорее всего, что справа все полюса простые, а слева -- кратные. И тогда никакой ТФКП не нужно даже формально.

Да так и есть. Верно над любым полем нулевой характеристики.

[ewert]

nnosipov в сообщении #693676 писал(а):

Да так и есть. Верно над любым полем нулевой характеристики.

Ну прям-таки. Функции-то вещественны, и тогда эта логика формально не проходит. Возиться же с алгебраическими замыканиями -- совсем неэстетично, учитывая заведомую очевидность ответа.

[nnosipov]

ewert в сообщении #693682 писал(а):

Функции-то вещественны, и тогда эта логика формально не проходит. Возиться же с алгебраическими замыканиями -- совсем неэстетично

Переход к алгебраическому замыканию удобен, но можно и без него обойтись и считать кратности неприводимых (над данным полем) сомножителей.

[Sergic Primazon]

dm в сообщении #693504 писал(а):

4. Let $x_1,\ldots,x_n,c>0$. Prove the inequality

$$\[\sqrt{{x_1+\sqrt{{x_2+\sqrt{{\ldots+\sqrt{x_n+c}}}}}}}<\sqrt{{x_1+\sqrt{{x_2+\sqrt{{\ldots+\sqrt{x_n}}}}}}}+\dfrac{c}{2^n\,\sqrt{{x_1\ldots x_n}}}\,\,.\]$$

(Ivan Feshchenko)

$f(c)=\[\sqrt{{x_1+\sqrt{{x_2+\sqrt{{\ldots+\sqrt{x_n+c}}}}}}}$ - concave function. So : $f(c) \le f(0)+c f'(0)$ and $f'(0) < \frac{1}{2^n} \frac{1}{\sqrt{{x_1\ldots x_n}}}}$

[nnosipov]

dm в сообщении #693504 писал(а):

7. An integer is called good if it is the $k$-th power of an integer for some $k\ge 2$. Is finite or infinite the set of all integers that are not sums of two good integers?

Суммой двух квадратов не представляется любое число вида $4n+3$. А различных сумм вида $a^k+b^l$, где $k>2$ или $l>2$, мало. Поэтому "infinite".

[Keter]

dm в сообщении #693504 писал(а):

1. Find all such continuous functions $f:[1,2]\to[1,2]$ that $f(1)=2$ and $f(f(x))f(x)=2$ for all $x\in[1,2]$. (Ivan Feshchenko)

Функция непрерывна и $f(2)=1,$ значит, она сюръективна. $D(f)=E(f),$ тогда пусть $f(x)=a.$ Имеем $f(a)=\dfrac{2}{a},$ откуда $f(x)=\dfrac{2}{x}.$
При проверке: $\dfrac{2}{\frac{2}{x}} \cdot \dfrac{2}{x}=2.$

Ответ: $f(x)=\dfrac{2}{x}.$