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

[bot]

Олимпиада НГУ - 2007 (1-3 курс). Воскресенье 30 сентября.

1) Сколько точек с целыми координатами и с расстояниями, кратными 7 до начала координат, расположены в круге $x^2+y^2 \le 111^2$?

2) Найти все действительные корни уравнения $x=\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+2}}}}}$

3) Пусть $a$ и $b$ --- положительные числа, $n$ --- натуральное. Доказать, что

$(n+1)(a^{n+1}+b^{n+1})\geq (a+b)(a^{n}+a^{n-1}b+ \dots +b^{n})$

4) Пусть функция $f$ --- монотонно возрастающая в нестрогом смысле на отрезке $[0,1]$ функция. Доказать, что

$$\int_0^1 f(x)dx \le 2\int_0^1 xf(x)dx $$

5) Последовательность $x_n$ задана рекуррентной формулой: $x_1 = a, \ \ x_{n+1}= \frac{100}{n}+\sin x_n$

Доказать, или опровергнуть, что она сходится при любом $a\in \mathbb{R}.$

[Руст]

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

[bot]

Помнится в прошлом году тоже начали с оценки тривиально.

Нет проблем дать задачу, которую за 4 часа не решит ни один младшекурсник.
Гораздо сложнее составить сбалансированный вариант, имеющий целью подбор команды для следующего тура.
С этой точки зрения не имеет смысла включать как всеми решаемые задачи, так и задачи, которые не решит никто.
Только что закончили проверку - расслоением вполне удовлетворён.

[Юстас]

А как 3ю без индукции решить? Что-нибудь совсем простое должно быть.

[Руст]

3-я решается легко дифференцированием, например поделим на меньшее в n+1 - ой степени и обозначив за х отношение большей на меньшее и умножив на (x-1) получим P(x)>=0 при х>=1. При этом P(1)=P'(1)=0, P''(x)>0, что и доказывает. Есть и другие методы решения.

[Юстас]

Это не намного отличается от индукции в том смысле, что не показывает суть неравенства, то есть как его можно получить, не зная изначально.

[Руст]

Вряд ли индукцией проще. Тут дифференцированием есть ещё одно преумещество, доказывается не только для натуральных n, но и для произвольных действительных n>=1 доопределив $a^n+a^{n-1}b+...+b^n=\frac{a^{n+1}-b^{n+1}}{a-b}$ (правая часть определена при любых действительных n).

[Юстас]

Мне все же кажется, что должно быть несложное "конструктивное" решение, позволяющее получить неравенство путем последовательных оценок при данной только левой или правой части.

[TOTAL]

Юстас писал(а):

Мне все же кажется, что должно быть несложное "конструктивное" решение, позволяющее получить неравенство путем последовательных оценок при данной только левой или правой части.

$(a^{k}-b^{k})(a^{n+1-k}-b^{n+1-k}) \geq 0, \; k=0,...,n+1$
$a^{n+1}+b^{n+1} \geq a^{n+1-k}b^k+a^kb^{n+1-k}$
Сложить эти неравенства будет конструктивно?
(Первым пришло решение с дифференцированием)

[Юстас]

TOTAL писал(а):

$a^{n+1}+b^{n+1} \geq a^{n+1-k}b^k+a^kb^{n+1-k}$

А это откуда?

[TOTAL]

Юстас писал(а):

TOTAL писал(а):

$a^{n+1}+b^{n+1} \geq a^{n+1-k}b^k+a^kb^{n+1-k}$

А это откуда?

Посмотрите чуть выше.

[Юстас]

Да, спасибо, это и есть то конструктивное решение, которое я хотел увидеть.

[Sasha Rybak]

Третья - это задачка на неравенство Мюрхеда
$a^kb^{n-k}+a^{n-k}b^k \ge a^lb^{n-l}+a^{n-l}b^l$, где $a,b \ge 0,\ 0 \le k \le l \le n/2$. Оно обобщается на любое количество переменных, но здесь это не нужно. :)

Мне понравилась задачка 1. Желательно применить неочевидный факт, что если $a^2+b^2$ делится на простое $p=4k+3$, то a и b в отдельности делятся на p. Для p=7 это проверяется несложным перебором. Но догадаться до такого упрощения, не зная соответствующую теорему теории чисел, не очень просто.

[bot]

Sasha Rybak писал(а):

Третья - это задачка на неравенство Мюрхеда ...
Мне понравилась задачка 1. Желательно применить неочевидный факт, что если $a^2+b^2$ делится на простое $p=4k+3$, то a и b в отдельности делятся на p. Для p=7 это проверяется несложным перебором. Но догадаться до такого упрощения, не зная соответствующую теорему теории чисел, не очень просто.

Третья и предполагалась как многовариантная в смысле решений. Если через дифференцирование, то это поиск экстремума непрерывной функции на отрезке [0,1]. Решений было много, в том числе и индукцией.
В первой сама постановка неминуемо должна привести к исследованию делимости на 7 суммы квадратов, так что догадаться до упрощения несложно. А 7 было выбрано, чтобы не осложнять возможность перебора остатков. Первый курс ещё не знает квадратичных вычетов, а 2-3 уже подзабыли.
Меня интересует мнение по поводу последней. Сложной её, конечно, не назовёшь - два простых хода. Но что-то мне не показались эти ходы совсем уж простыми, потому и поставил задачу на 5-е место. Результат проверки подтвердил - она оказалась самой нерешаемой.

[Руст]

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