IMO 2009

[arqady]

В Бремене 15-16.07.09 прошла очередная международная математическая олимпиада школьников.
Россия заняла 3- е место, Израиль - 46- е.
Здесь можно посмотреть задачи.

[dewgong]

Странно получилось то....
Туркмения, Узбекистан и даже Таджикистан выступили лучше Израиля. На сколько я помню такого не случалось

[tajik]

dewgong в сообщении #230438 писал(а):

даже Таджикистан выступили лучше Израиля.

Ну и что? Таджики хуже евреев что ли?

dewgong в сообщении #230438 писал(а):

На сколько я помню такого не случалось

А это потому что Таджикистан всего лишь 4 -ый год участвует! Через несколько лет не удивляйтесь если Таджикистан выступает лучше России или даже лучше Китая!

[Батороев]

tajik в сообщении #230506 писал(а):

Через несколько лет не удивляйтесь если Таджикистан выступает лучше России или даже лучше Китая!

Что, точно???!!!
Ну, смотрите, за язык Вас никто не тянул.

[Джек]

Украина FOREVER-у нас 14 место(3 золотых !!!)=)

[Cave]

1) Из условия $a_i\equiv a_i a_{i+1}$, тогда $a_1\equiv a_1 a_2\equiv a_1 (a_2 a_3)\equiv a_1 a_2 a_3\equiv a_1 a_ 2 (a_3 a_4) \equiv\ldots\equiv a_1 a_2 a_3 \ldots a_k := P$.
Предположим противное, тогда $a_k\equiv a_k a_1$, тогда аналогичную цепочку сравнимостей можно начать с любого элемента $a_i$, например, с $a_2$. Но тогда $a_2\equiv P\equiv a_1$, а так как $1\leqslant a_i\leqslant n$, то $a_1 = a_2$ - противоречие с условием.

-- Чт июл 23, 2009 00:13:54 --

5) $f(n) = n$, если я ничего не напутал.
Положим $a=1$, получим тройку $\{1, f(b), f(b + f(1) - 1))\}$, которая является множеством длин сторон некоторого треугольника. Из неравенства треугольника получаем $f(b) = f(b + f(1) - 1)$. Если $f(1)\ne 1$, то положим $f(1) = k+1,k\geqslant 1$, тогда $f(b) = f(b + k)$, то есть $f$ является $k$-периодичной. Положим $a = 3k+1, b = 1$, получим тройку $\{3k+1, k+1, k+1\}$, в которой $3k+1\geqslant (k+1)+(k+1)$ - противоречие. Значит, $f(1)=1$.
Положим $b=1$, получим тройку $\{a, 1, f(f(a))\}$, откуда $f(f(a)) = a$. Значит, все $\mathbb{N}$ разбивается на две части: числа $n$, для которых $f(n) = n$, и пары чисел $(n,m)$, где $n\ne m$, таких что $f(n) = m, f(m) = n$.
Предположим, что $f$ не является тождественной, тогда вторая часть непуста. Выберем наименьшее число $m$, участвующее в парах второй части, положим $n = f(m)$. Если $m\geqslant 3$, то положим $a = 2, b = m - 1$ - числа из первой части, для которых $f(a) = a, f(b) = b$; получаем тройку $\{2, m - 1, n\}$, в которой $2 + (m - 1) = m+1 \leqslant n$ - противоречие. $m$ не может быть единицей, так как $f(1)=1$, значит, $m=2$; По-прежнему $f(2) = n\geqslant 3$. Положим $a=2, b=n$, получим тройку $\{2, 2, f(2n - 1)\}$, откуда $f(2n - 1)\leqslant 3$. $f$ - биекция, $f^{-1}(1)=1, f^{-1}(2)=n<2n - 1$, поэтому $f(2n - 1) = 3$, откуда $f(3) = 2n - 1$. Теперь положим $a = 3, b = n$, получим тройку $\{3, 2, f(3n - 2)\}$. Аналогично получаем, что $f(3n - 2) = 4$. Продолжая далее, имеем $f(dn - (d-1)) = d+1$ и наоборот: $f(d+1)=dn-(d-1)$ для $d\in\mathbb{N}$. Положим $d = n-1$, получим $f(n) = (n-1)n-(n-1-1)=n^2-2n+2 > 2$, так как $n>2$. Противоречие с тем, что $f(n) = 2$.
Значит, вторая часть пуста, первая часть совпадает с $\mathbb{N}$, откуда $f(n)\equiv n$.

[Sonic86]

Вот мои небольшие соображения по поводу задачи 3.
3. Буду писать $s(n)$ вместо $s_n$.
По условию $s(s(n))$ и $s(s(n)+1)$ - арифметические прогрессии, значит $s(s(n))=a+bn, s(s(n)+1)=c+dn$. Поскольку $s(n)$ - строго возрастающая, то $(\forall n) s(n) \geq n$ и значит $\lim\limits_{n \to \infty} s(n) = + \infty$
Рассмотрим $\lim\limits_{n \to \infty} \frac{s(n)}{n}$. Если предположить, что $\lim\limits_{n \to \infty} \frac{s(n)}{n} = + \infty$, то $\lim\limits_{n \to \infty} \frac{s(s(n))}{n} \geq \lim\limits_{n \to \infty} \frac{s(n)}{n} = + \infty$, что противоречит условию: $\lim\limits_{n \to \infty} \frac{s(s(n))}{n} = b$. Значит $\lim\limits_{n \to \infty} \frac{s(n)}{n} = k$, то есть $s(n)=kn+t(n), \lim\limits_{n \to \infty} \frac{t(n)}{n} = 0$.
Найдем $b,d$ через $c$:
$s(s(n))=k^2n+kt(n) + t(s(n)) \Rightarrow b = \lim\limits_{n \to \infty} \frac{s(s(n))}{n} = k^2 + k \lim\limits_{n \to \infty} \frac{t(n)}{n} + \lim\limits_{n \to \infty} \frac{t(s(n))}{n}$
$\lim\limits_{n \to \infty} \frac{t(n)}{n} = 0$, а $\lim\limits_{n \to \infty} \frac{t(s(n))}{n} = \lim\limits_{n \to \infty} \frac{t(s(n))}{s(n)} \cdot \frac{s(n)}{n} = 0 \cdot k = 0$.
То есть $b=k^2$, аналогично из условия $s(s(n)+1)=c+dn$ получаем $d=k^2$, откуда $b=d$ и значит $s(s(n)+1)-s(s(n))=c-a$.
Так как $s(n)=kn+t(n)$, то $s(s(n)+1)-s(s(n))=k(s(n)+1-s(n))+t(s(n)+1)-t(s(n))=c-a \Leftrightarrow t(s(n)+1)-t(s(n))=c-a-k = R$. Обозначая $m=s(n), m \to + \infty$, получаем $\lim\limits_{m \to \infty} (t(m+1)-t(m)) = R$, то есть $t(m+1)-t(m)=R + \alpha(m), \lim\limits_{m \to \infty} \alpha (m) =0$. Поскольку $k$ - целое (не доказано!), то $t(n)=s(n)-kn$ - целочисленная, и тогда $\alpha (m) = t(m+1)-t(m)-R$ - целочисленная, значит из $\lim\limits_{m \to \infty} \alpha (m) =0$ следует, что для $m \geq m_0 \ \alpha (m) = 0$. Значит, для $m \geq m_0$ $t(m+1)=t(m)+R$, значит $(\forall r) t(m+r)=t(m)+ Rr$, значит $t(2m)=t(m)+mR$, значит $0 = \lim\limits_{m \to \infty} \frac{t(2m)}{2m} = \frac{1}{2}(R+0)$, откуда $R=0$ и значит для всех $m \geq m_0$ выполняется $t(m+1)=t(m)=T$.
Таким образом, для $n \geq n_0 \ s(n) = kn + T$.

То есть доказательство далеко не полное.
Есть какие-нибудь еще идеи?

[Sonic86]

P.S. Интересно, является ли условие $s(s(n)+1)=c+dn$ необходимым для $s(n) = kn+T$?
Я попытался найти $s(n)$ такую, что $s(s(n))$ - арифметическая прогрессия, а $s(n)$ - нет. Нашел $s(n)=2+n+(-1)^n$, но она не является строго возрастающей.

[ИСН]

Там кусочно-линейную можно было замостырить, кажется.

[Sonic86]

ИСН писал(а):

Там кусочно-линейную можно было замостырить, кажется.

А можно пример? Я вот тоже сначала так думал, может не допер

[albega]

По задаче 5 есть чуть более красивое решение:
Уже доказано, что $f(1)=1, f(f(a))=a$
$a=2$, следовательно $|f(b+f(2)-1)-f(b)|<2$
$f(b+f(2)-1)-f(b)=0$, $f(2)=1$, $2=f(f(2))=f(1)=1$, противоречие
$f(b+f(2)-1)-f(b)=-1$, подставим $b=1$, $f(f(2))=0$, противоречие
Итак, $f(b+f(2)-1)-f(b)=1$
Пусть $f(2)-1=c$, следовательно $f(b+c)=f(b)+1$, для любых натуральных $b$
По индукции $f(b+ck)=f(b)+k$, для любых натуральных $b,k$
$b+kc=f(f(b+kc))=f(f(b)+k)$
$k=c$, $b+c^2=f(f(b)+c)=f(f(b))+1=b+1$
$c=1$, следовательно $f(b+k)=f(b)+k$, для любых натуральных $k$
$b=1$, $f(k+1)=k+1$