17th IMC, Blagoevgrad, Bulgaria, 24th - 30th July 2010

[arqady]

Первый день
Problem 1. Let $0<a<b.$ Prove that

$$\int_a^b(x^2+1)e^{-x^2}dx\geq e^{-a^2}-e^{-b^2}$$

Problem 2.Compute the sum of the series

$$\sum_{k=0}^{\infty} \frac1{(4k+1)(4k+2)(4k+3)(4k+4)}=\frac{1}{1\cdot 2 \cdot 3 \cdot 4} +\frac{1}{5\cdot 6 \cdot 7 \cdot 8} +\dots$$

Problem 3. Define the sequence $x_1,x_2,\dots$ inductively by $x_1=\sqrt{5}$ and $x_{n+1}=x^2_n-2$ for each $n\geq 1.$ Compute

$$\lim_{n\to \infty} \frac{x_1\cdot x_2\cdots x_3\dots x_n}{x_{n+1}}$$

Problem 4. Let $a,b$ be two integers and suppose that $n$ is a positive integer for which the set $\mathbb{Z}\setminus \{ ax^n+by^n\, | \, x,y \in \mathbb{Z} \}$is finite.
Prove that $n=1.$

Problem 5. Suppose that $a,b,c$ are real numbers in the interval $[-1,1]$ such that

$$1+2abc\geq a^2+b^2+c^2$$

Prove that

$$1+2(abc)^n\geq a^{2n}+b^{2n}+c^{2n}$$

for all positive integers $n.$

Duration is probably 5 hours and each problem is given 10 points.

Второй день
Problem 1. $(a)$ A sequence $x_1,x_2,\dots$ of real numbers satisfies

$$x_{n+1}=x_n \cos x_n \textrm{ for all } n\geq 1$$

Does it follows that this sequence converges for all initial values $x_1?$ (5 points)

$(b)$ A sequence $y_1,y_2,\dots$ of real numbers satisfies

$$y_{n+1}=y_n \sin y_n \textrm{ for all } n\geq 1$$

Does it follows that this sequence converges for all initial values $y_1?$ (5 points)

Problem 2. Let $a_0,a_1,\dots,a_n$ be positive real numbers such that $a_{k+1}-a_k \geq 1$ for all $k=0,1,\dots,n-1.$ Prove that

$$1+\frac{1}{a_0} \left( 1+\frac1{a_1-a_0}\right)\cdots\left(1+\frac1{a_n-a_0}\right)\leq \left(1+\frac1{a_0}\right) \left(1+\frac1{a_1}\right)\cdots \left(1+\frac1{a_n}\right)$$

(10 points)

Problem 3. Denote by $S_n$ the group of permutations of the sequence $(1,2,\dots,n).$ Suppose that $G$ is a subgroup of $S_n,$ such that for every $\pi\in G\setminus\{e\}$ there exists a unique $k\in \{1,2,\dots,n\}$ for which $\pi(k)=k.$ (Here $e$ is the unit element of the group $S_n.$) Show that this $k$ is the same for all $\pi \in G\setminus \{e\}.$ (10 points)

Problem 4. Let $A$ be a symmetric $m\times m$ matrix over the two-element field all of whose diagonal entries are zero. Prove that for every positive integer $n$ each column of the matrix $A^n$ has a zero entry.(10 points)

Problem 5. Suppose that for a function $f: \mathbb{R}\to \mathbb{R}$ and real numbers $a<b$ one has $f(x)=0$ for all $x\in (a,b).$ Prove that $f(x)=0$ for all $x\in \mathbb{R}$ if

$$\sum^{p-1}_{k=0}f\left(y+\frac{k}{p}\right)=0$$

for every prime number $p$ and every real number $y.$ (10 points)

Duration: 5 hours

(имхо)

Минимум пять задач (в первый день: 1,2,3,5 и во второй день: 2) доступны средним школьникам. Всё это выглядит как розыгрыш, но вроде бы именно эти задачи и были.

[neo66]

arqady в сообщении #341246 писал(а):

Первый день
Problem 1. Let $0<a<b.$ Prove that

$$\int_a^b(x^2+1)e^{-x^2}dx\geq e^{-a^2}-e^{-b^2}$$

$\int_a^b(x^2+1)e^{-x^2}dx\geq \int_a^b 2xe^{-x^2}dx =e^{-a^2}-e^{-b^2}$

-- Ср июл 28, 2010 21:34:55 --

arqady в сообщении #341246 писал(а):

Второй день
Problem 1. $(a)$ A sequence $x_1,x_2,\dots$ of real numbers satisfies

$$x_{n+1}=x_n \cos x_n \textrm{ for all } n\geq 1$$

Does it follows that this sequence converges for all initial values $x_1?$ (5 points)

$(b)$ A sequence $y_1,y_2,\dots$ of real numbers satisfies

$$y_{n+1}=y_n \sin y_n \textrm{ for all } n\geq 1$$

Does it follows that this sequence converges for all initial values $y_1?$ (5 points)

(a) Последовательность не сходится, например, при $x_1=\pi$.

(b) Думаю, что последовательность сходится всегда, но сторого доказать не могу, видимо не дорос до среднего школьника.

[arqady]

neo66 в сообщении #341358 писал(а):

... видимо не дорос до среднего школьника.

Попробуйте неравенство из второго дня. Обычная индукция.
Вторая задача первого дня. Сумма бесконечной геометрической прогрессии с примитивным интегралом.
Пятая задача первого дня. Здесь сумма геометрической прогрессии и можно применить неравенство Коши-Шварца и переписать условие похожим на этот способом.
Здесь можно посмотреть предварительные (перед апелляциями) результаты олимпиады.

[neo66]

arqady в сообщении #341246 писал(а):

Первый день

Problem 2.Compute the sum of the series

$$\sum\limits_{k=0}^{\infty} \frac1{(4k+1)(4k+2)(4k+3)(4k+4)}=\frac{1}{1\cdot 2 \cdot 3 \cdot 4} +\frac{1}{5\cdot 6 \cdot 7 \cdot 8} +\dots$$

$$\sum\limits_{k=0}^{\infty} \frac1{(4k+1)(4k+2)(4k+3)(4k+4)}= \frac 1 6 \sum\limits_{k=0}^{\infty}( \frac1{4k+1}- \frac3{4k+2}+\frac3{4k+3} - \frac1{4k+4})= \frac 1 6\int\limits_0^1 \frac {(1-x)^3}{1-x^4} dx= \frac 1 {24}(\ln 64 - \pi)$$

[Хорхе]

Вообще странно, что у текущего лидера против третьей задачи второго дня стоит единичка. Задача-то делается в пять строчек с использованием Бернсайда, который напрашивается сразу после прочтения условия. То есть кто прочел условие -- подумал про Бернсайда, кто подумал про Бернсайда -- решил, потому что решать в принципе нечего. Видимо, после апелляции единичка превратится в десятку?

[arqady]

Вот почти окончательные результаты (ещё могут быть незначительные изменения):
http://www.mediafire.com/?iuc863x5yvxp2un
Израиль занял четвёртое командное место!!!

[Хорхе]

А первые наши, однако, закономерность :)
И если в прошлом году отрыв от Ягайлова университета был смешной, то теперь уверенная победа.
Кстати, этот Пшемислав Мазур таки не решил третью задачу второго дня. Хорошая, конечно, фамилия. Впрочем, меня больше поразил Ласло Ловас (16-е место). Не потомок ли?

[neo66]

arqady в сообщении #341246 писал(а):

Первый день

Problem 5. Suppose that $a,b,c$ are real numbers in the interval $[-1,1]$ such that

$$1+2abc\geq a^2+b^2+c^2 $$

Prove that

$$1+2(abc)^n\geq a^{2n}+b^{2n}+c^{2n}$$

for all positive integers $n.$

Первое неравенство эквивалентно такому:

$$(1-a^2)(1-b^2)\ge (ab - c)^2 $$

(1)

а второе такому:

$$(1-a^{2n})(1-b^{2n}) \ge (a^nb^n - c^n)^2$$

(2)

или:

$$(1-a^{2})(1-b^{2})(1+a^2 \dots a^{2(n-1)})(1+b^2 +\dots +b^{2(n-1)}) \ge (ab - c)^2 ((ab)^{n-1}+ \dots +c^{n-1})^2$$

(3)

По неравенству Коши-Шварца:

$$(1+a^2 \dots a^{2(n-1)})(1+b^2 +\dots +b^{2(n-1)}) \ge (1+ \dots +|ab|^{n-1})^2$$

(4)
а, так как $|c|\le 1$

$$(1+a^2 \dots a^{2(n-1)})(1+b^2 +\dots +b^{2(n-1)}) \ge ((ab)^{n-1}+ \dots +c^{n-1})^2$$

(5)

Умножая почленно (5) на (1) получаем требуемое неравенство (2).

[arqady]

Вот здесь:
http://mathproblems123.wordpress.com/
можно посмотреть якобы официальное решение этой задачи.

[neo66]

Я не совсем понял решение. Верно ли, что, если матрица неотрицательно определена, то и матрица из энных степеней тоже неотрицательно определена?

[arqady]

neo66 в сообщении #342171 писал(а):

Я не совсем понял решение. Верно ли, что, если матрица неотрицательно определена, то и матрица из энных степеней тоже неотрицательно определена?

Ну для нашей конкретной матрицы мы это доказали.
Честно говоря, я его (официальное доказательство) совсем не понял. Поэтому и написал: "якобы".
Наверное, это очень просто. Но я не вижу. Надеюсь, придут более умные и всё объяснят...

[dm]

Хорхе в сообщении #341551 писал(а):

А первые наши, однако, закономерность :)
И если в прошлом году отрыв от Ягайлова университета был смешной, то теперь уверенная победа.

Ну, в прошлом году еще рейтинг Киевского университета был неправильно посчитан. Должно было быть:
1 Kyiv Taras Shevchenko National University 273.5 (вместо написанных 270,75)
2 Jagiellonian University 269,75
...
Но просить пересчитать мы не стали. Какая разница, так или так первые.

Хорхе в сообщении #341551 писал(а):

Впрочем, меня больше поразил Ласло Ловас (16-е место). Не потомок ли?

Сын. На Ярнике в этом году он тоже был: http://vjimc.osu.cz/node/2

[arqady]

dm, так это я Вашими ссылками пользовался?

[dm]

arqady
Фото мои, а ссылки общие

[Dandan]

neo66 в сообщении #342171 писал(а):

Я не совсем понял решение. Верно ли, что, если матрица неотрицательно определена, то и матрица из энных степеней тоже неотрицательно определена?

это свойство есть в википедии http://en.wikipedia.org/wiki/Positive-d ... properties
Небольшое гугление позволяет найти док-во: http://books.google.com.ua/books?id=f6_ ... em&f=false