Олимпиада НГУ - 2007

[bot]

Угу, первый ход можно и так сделать:
$\frac{100}{n-1}-1 \le x_n \le \frac{100}{n-1}+1 \Rightarrow -\frac{\pi}{2}\le x_n \le \frac{\pi}{2}$ для достаточно больших n. Здесь упускается положительность $x_n$ для достаточно больших номеров, но этого и не нужно.
А вот монотонность, хотя это и просто, но ведь не так, чтобы стандартно доказывается.
Мне эта задачка больше всех нравится - не моя, потому и свободен в оценках.

[TOTAL]

Руст писал(а):

Сразу получаем, что $0\le x_{101}\le 2$, соответственно, дальше sin всегда положителен и начиная с n=200 последовательность монотонно убывает до 0 в пределе.

Я бы не ставил на монотонное убывание.

Поскольку $0 \leq x_{101}=1+sin(x_{100}) \leq 2$, то дальше всегда $x_{n} > 0$.

Возьмем произвольное $ t > 0 $ и найдем $N$, для которого $d = \frac{100}{N} < t - sin(t)$.

$y_{N+1}=d+sin(x_{N})$
$y_{N+2}=d+sin(y_{N+1})$
$ \ldots $

$x_{N+1} \leq y_{N+1}$
$x_{N+2} \leq y_{N+2}$
$ \ldots $

$y_{n}$ сходится (это надо доказывать?) к $y^* < t $, поэтому при больших $n$ имеем $x_n < t $,
что означает сходимость исходной последовательности к нулю.

(Лучше бы, конечно, более короткое решение, но до короткого дольше думать)

[Руст]

TOTAL писал(а):

Руст писал(а):

Сразу получаем, что $0\le x_{101}\le 2$, соответственно, дальше sin всегда положителен и начиная с n=200 последовательность монотонно убывает до 0 в пределе.

Я бы не ставил на монотонное убывание.

На самом деле если $y_n=\phi(n)+sin(y_n)$, где $\phi(n)$ монотонно убывающая положительная функция, легко доказывается, что у_n монотонно убывает и стремится к 0. А $x_{n+1}$ от x_n получается приближением к y_n и уменьшением за счёт уменьшения $\phi(n)$ на $\phi(n)-\phi(n+1)$, отсюда следует, что x_n начиная с некоторого n становится больше y_n, тогда наступает монотонное убывание.

[bot]

TOTAL писал(а):

Лучше бы, конечно, более короткое решение, но до короткого дольше думать

Мне было проще додуматься до короткого - авторского решения я не знаю, теперь можно и спросить.

Первым ходом мы загнали синус в промежуток монотонности $[-\pi/2, \pi/2]$, хотя можно было уполовинить промежуток, первоначально я так и делал, начав с номера 101, а потом заметил, что второй ход позволяет обойтись без этого.
Берём утверждение "начиная с некоторого места, последовательность убывает" . Из-за убывания первого слагаемого в этом утверждении работает индуктивный переход. Поэтому если ещё будет база индукции, то утверждение получит доказательство по индукции. Если же базы для индукции нет, то это означает, что последовательность возрастает. Ограниченность у нас есть, поэтому всё.
Нерелизуемость возрастания при таком подходе становится понятной апотом: предел ясно 0 и остаётся обнаружить положительность, начиная с некоторого места.

P.S.Последовательность $\frac{100}{n}$ очевидно можно заменить на любую монотонную, сходящуюся к произвольному числу интервала $(1-\pi/2, \pi/2-1))$

[TOTAL]

bot писал(а):

P.S.Последовательность $\frac{100}{n}$ очевидно можно заменить на любую монотонную, сходящуюся к произвольному числу интервала $(1-\pi/2, \pi/2-1))$

Заменим на $x_{n+1}=d_n+f(x_n)$, где $d_n$ просто сходится,
$f(x)$ сжимающая монотонная, отображение "в себя" есть.
Как сработает ускоренное решение?

[bot]

Ускоренное решение - это то, которое я привёл?
Для индукционного перехода на втором шаге существенно использовалась монотонность $d_n$.

[Sasha Rybak]

По-моему, монотонность в задаче 5 доказать гораздо труднее, чем сходимость к 0.

Сходимость к 0 легко осознать по аналогии с задачкой о гусенице (гусеница за день на поднимается на сколько-то метров, а за ночь сползает на сколько-то метров...). То есть, при больших n элемент x_n не может быть далеко от 0, поскольку иначе замена $x_n \rightarrow \sin x_n$ сильно опускала бы вниз, а подъём на 100/n уже не мог бы компенсировать спуск.

Монотонность для n>100 проверил программно. Также заметил, что вне зависимости от начального x_1, получаем $x_{101} \approx 1,9326179766$. Это следствие сжимающести отбражения $x \rightarrow b+\sin x$.
Но для монотонности $\{x_n\}$ недостаточно монотонности 100/n. Нужна ещё и некоторая "однообразность" этой функции, позволяющая накладывать двусторонние условия. Представьте, например, что 100/n для n>100 заменили на 100000/(99900+n). Тогда получим небольшой скачок: $\sin x_{101}+100000/100001 \approx 1,9352535509$.

[TOTAL]

Sasha Rybak писал(а):

Также заметил, что вне зависимости от начального x_1, получаем $x_{101} \approx 1,9326179766$. Это следствие сжимающести отбражения $x \rightarrow b+\sin x$.

Сжимает, да не сильно. Задача $x_{n+1}=a_n+f(x_n)$ перестает быть олимпиадной,
если $a_n$ -- произвольная сходящаяся, а функция $f(x)$ -- произвольная сжимающая с коэффициентом $q<1$.

[bot]

Sasha Rybak писал(а):

По-моему, монотонность в задаче 5 доказать гораздо труднее, чем сходимость к 0.

О-оп-с, я посчитал, что понятно написал. Или Вы не об этом?
На всякий случай давайте подробно для рекуррентности
$x_{n+1}=a_n + \sin x_n$, где $a_n$ монотонно сходится к $a \in (1-\frac{\pi}{2}, \frac{\pi}{2}-1)$.

Отбрасывая, если надо конечное число номеров, мы можем считать, что
$1-\frac{\pi}{2} < a_n < \frac{\pi}{2}-1$ для всех $n$, а следовательно и $-\frac{\pi}{2}< x_n < \frac{\pi}{2}$.
Докажем, что $x_n$ монотонна, начиная с некоторого места.
Пусть $a_n$ возрастающая. Если существует номер $n_0$ для которого $x_{n_0+1}\ge x_{n_0}$, то это база индукции для утверждения
«$x_n$ возрастает, начиная с $n_0$».
Индуктивный переход: если $x_{n}\ge x_{n-1}$, то $x_{n+1}=a_n + \sin x_n \ge a_{n-1} + \sin x_{n-1}=x_n$.
Если же такого номера не существует, то $x_{n+1}< x_n$ для всех $n$, то есть $x_n$ убывающая.
Аналогично, если $a_n$ убывает и есть база индукции для утверждения «$x_n$ убывает, начиная с $n_0$». то это утверждение доказуемо по индукции, а в случае отсутствия базы $x_n$ возрастающая.

Добавлено спустя 7 минут 39 секунд:

Пока писал и редактировал (да ещё и не в тот форум для просмотра закидывал ) TOTAL вклинился.
Согласен, если отправить в игнор монотонность $a_n$, то задача станет просто тяжёлой и совсем не олимпиадной.

[TOTAL]

bot писал(а):

Пока писал и редактировал (да ещё и не в тот форум для просмотра закидывал ) TOTAL вклинился.
Согласен, если отправить в игнор монотонность $a_n$, то задача станет просто тяжёлой и совсем не олимпиадной.

Согласен в смысле не согласен.
Так как задача сразу сведется к доказательству того, что $|y_n| \rightarrow 0$, если $|y_{n+1}| \leq |t_n| + q|y_{n}|$, $t_n \rightarrow 0$.
Это в несколько раз легче, чем исходная задача.

[Sasha Rybak]

bot писал(а):

О-оп-с, я посчитал, что понятно написал. Или Вы не об этом?
На всякий случай давайте подробно для рекуррентности
$x_{n+1}=a_n + \sin x_n$, где $a_n$ монотонно сходится к $a \in (1-\frac{\pi}{2}, \frac{\pi}{2}-1)$.

Отбрасывая, если надо конечное число номеров, мы можем считать, что
$1-\frac{\pi}{2} < a_n < \frac{\pi}{2}-1$ для всех $n$, а следовательно и $-\frac{\pi}{2}< x_n < \frac{\pi}{2}$...

Я-а-а-сненько. Я же исследовал монотонность, начиная с n=101, то есть когда $a_n<1$. В этом случае $x_{101} \notin (-\frac{\pi}{2}, \frac{\pi}{2})$.

[Padawan]

Руст писал(а):

Задачи простые. На решение в уме ушло 5-6 мин. на всё.

Я в шоке

[bot]

TOTAL писал(а):

Согласен в смысле не согласен.
Так как задача сразу сведется к доказательству того, что $|y_n| \rightarrow 0$, если $|y_{n+1}| \leq |t_n| + q|y_{n}|$, $t_n \rightarrow 0$.
Это в несколько раз легче, чем исходная задача.

Легче или нет - познаётся в сравнении. Простоту логического трюка, который отрицание монотонности в одном смысле превращает в монотонность в противоположном смысле, я показал. А у Вас каким-то образом, если я правильно понимаю, $\lim y_n =0$ вытекает из следующей посылки:

$0 \le y_{n+1} \le t_n + qy_{n}, \ \ 0 < q < 1, \ \ t_n \rightarrow 0^+$.

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

Впервые с подобным логическим трюком я познакомился ещё в школе.

И да простят меня модераторы:
[offtop]
Расправившись с иррациональностью числа $\sqrt2$ приступаю к задаче:
Доказать, что существуют иррациональные $x$ и $y$, для которых $x^y$ рационально.
Недолго думая, беру $x=\sqrt2^{\sqrt2}, \ \ y=\sqrt2$ и пытаюсь доказать, что $x$ иррационально. Не помню сколько я мучился, пока не понял, что этого и не нужно.
[/offtop]

[bot]

МЕЖВУЗОВСКАЯ ОЛИМПИАДА ПО МАТЕМАТИКЕ 2007 г.
ДЛЯ ВУЗОВ МАТЕМАТИЧЕСКОГО ПРОФИЛЯ.

http://mmfd.nsu.ru/mmf/olimp/07/ol07r.htm

1) Доказать, что в десятичной записи числа $2^{797}$ по крайней мере одна цифра повторяется не менее 25 раз.

2) В пространстве расположено 2007 точек. Доказать, что через одну из этих точек можно провести такую плоскость, что по обе стороны от неё окажется ровно по 1003 точки.

3) На отрезке $[0,1000]$ лежат 11 точек. Доказать, что среди них найдутся две точки $x$ и $y$, удовлетворяющие неравенству $|x-y|\leqslant 1+3\sqrt[3]{xy}. $

4) По краю леса идёт прямолинейная дорога. Находясь на дороге, Петя по телефону назначил Ане свидание у кривой берёзы в лесу и сказал, что придёт максимум через час. Определить все возможные положения кривой берёзы, если известно, что Петя может идти по дороге со скоростью 5 км/час, а по лесу - со скоростью 3 км/час.

5) Доказать сходимость и найти предел последовательности, заданной рекуррентностью:

$$x_0=a, \ x_1=b, \ \ x_n=\frac{1}{n}x_{n-1}+\frac{n-1}{n} x_{n-2}, \ n=2,3,\ldots $$

[Руст]

Все задачи очень простые, на 5 мин. в общей сложности. Пожалуй интереснее 4 задачка ограничивается частью окружности радиуса 3 и касательным к нему из точки отстоящей на расстоянии 5ю
5 простая

$$x_n=a+(a-b)\sum_{k=1}^n\frac{(-1)^k}{k}.$$