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

[bot]

Shadow, круто! Так и знал, что недокрутил условие.

[bot]

31 ОБЛАСТНАЯ ОТКРЫТАЯ СТУДЕНЧЕСКАЯ ОЛИМПИАДА 2013г
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

1 курс

1. Положительные числа $x, y, z$ удовлетворяют равенствам $xyz=1$ и $x+y+z=\frac1x+\frac1y+\frac1z$. Найдите среднее из них.

2. Можно ли число 600 разложить в сумму 9 целых положительных слагаемых так, чтобы всевозможные суммы этих слагаемых, взятых не более одного раза, были различны?

3. Пусть $a_n=\dfrac{1}{4^n+1}+\dfrac{2}{4^n+3}+\dfrac{2^2}{4^n+3^2}\ldots +\dfrac{2^{n-1}}{4^n+3^{n-1}}$. Вычислите $\lim\limits_{n\to\infty}2^na_n.$

4. У мухи один носок и одна туфелька на каждую из её шести ножек. Сколько различных порядков обувания возможно, если считать, что муха никогда не наденет туфельку на голую ногу, а носок - поверх туфельки?

5. Целые положительные числа $a, b , c , d$ удовлетворяют равенству $ab=cd$. Может ли число $a+b+c+d$ быть простым числом?

Вузы математического профиля, 2-4 курсы

1. На конечном множестве $G$ задана ассоциативная операция $\cdot$. Докажите что в $G$ существует идемпотент (то есть элемент $x$, удовлетворяющий тождеству $xx=x$).

2. Существует ли непрерывная функция $f:\mathbb R\to\mathbb R$, удовлетворяющая тождеству

$$f(f(x))=e^{-x}\, ?$$

3. Даны две непрерывные функции $f, g : [a;b] \to [a;b]$, причём $f(g(x))=g(f(x))$ при всех $x \in [a;b]$.
Множество неподвижных точек функции $f$ связно. Докажите, что $f$ и $g$ имеют общую неподвижную точку.
(Точка $c$ называется неподвижной точкой функции $f$, если $f(c)=c$).

4. Пусть вещественная функция $f$ непрерывна на $[a; b]$, дифференцируема во внутренних точках и $f(a)=0$. Докажите неравенство

$$\int\limits_a^b |f(x)|^2\, dx\leqslant \dfrac{(b-a)^2}{2}\int\limits_a^b |f'(x)|^2\, dx$$

5. Найдите все тройки ортогональных матриц $P, Q $ и $R$ порядка $2$, удовлетворяющих равенству $P+Q=R$.

Вузы нематематического профиля, 2-4 курсы

1. Определите знак выражения $\sum\limits^{n-1}_{k=1}\sin\left(\cos\frac{k\pi }{n}\right)$.

2. Докажите, что $\sum\limits_{k=0}^n(k+1)C_n^k=2^{n-1}(n+2)$ %$\sum\limits_{k=0}^n(-1)^{k}(k+1)C_n^k=0$

3. Исследуйте сходимость ряда $\sum\limits_{n=1}^\infty n!\left(\frac{a}{n}\right)^n$ при $a\in \mathbb R$.

4. В корзине лежат 12 различных пар носок. Какова вероятность, что среди 4 наугад выбранных носков окажется хотя бы одна пара?

5. Докажите неравенство

$$\dfrac{1}{\sqrt{n}}+\dfrac{1}{\sqrt{n+1}}+ \ldots + \dfrac{1}{\sqrt{n^2-1}}>2\left(n-\sqrt n\right)$$

[ewert]

bot в сообщении #780674 писал(а):

5. Найдите все тройки ортогональных матриц $P, Q $ и $R$ порядка $2$, удовлетворяющих равенству $P+Q=R$.

$(P\vec u, Q\vec u)=-\frac12(\vec u,\vec u)$, т.е. $Q^{-1}P$ -- это поворот на $\pm120^{\circ}$.

[bot]

(Оффтоп)

К задаче #4 за 1 курс. Люди не только любуются мухами, но и ловят их, причем на поимку одной мухи среднестатистический человек тратит столько же калорий, сколько при средненьком половом акте, а при положительном результате получает сопоставимое удовольствие. Муха — это маленькая птичка (один грузин сказал). По научному, но популярно, муха (лат. Musca) имеет два крыла и, по мнению Аристотеля, 8 лапок, а по новейшим исследованиям - 6 ножек (сексуальных). Любитель всякого ... Объект охоты для домохозяек. Огнестрельное оружие для охоты не рекомендуется.

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

это поворот на $\pm120^{\circ}$

Возможно чисто геометрическое решение (интересно, будут ли они?).
Порядок изменил на 2 в последний момент - обошёл все аудитории и сказал, пожалел ...

[ewert]

bot в сообщении #780740 писал(а):

Возможно чисто геометрическое решение (интересно, будут ли они?).

Ну у меня на самом деле тоже геометрические соображения неявно присутствуют. Почему, собственно, это именно чистый поворот?... Кроме соображений непрерывности чего-то ничего простого в голову не приходит. Конечно, достаточно и просто соображений непрерывности, чтобы с самого начала утверждать, что это поворот.

Насчёт увеличения порядка, хм... Если человек помнит про разложение пространства в двумерные инвариантные подпространства, то для него такое обобщение будет означать не столько усложнение решения, сколько зануднение ответа.

bot в сообщении #780674 писал(а):

4. Пусть вещественная функция $f$ непрерывна на $[a; b]$, дифференцируема во внутренних точках и $f(a)=0$. Докажите неравенство

$$\int\limits_a^b |f(x)|^2\, dx\leqslant \dfrac{(b-a)^2}{2}\int\limits_a^b |f'(x)|^2\, dx$$

Ну тупо в лоб: $\int\limits_0^1|f(x)|^2dx\leqslant\int\limits_0^1dx\left(\int\limits_0^x|f'(t)|\,dt\right)^2$, где $\int\limits_0^x|f'(t)|\,dt\leqslant\sqrt{x}\cdot\sqrt{\int\limits_0^x|f'(t)|^2dt}\leqslant\sqrt{x}\cdot\sqrt{\int\limits_0^1|f'(t)|^2dt}.$

А заменить двойку на точное $\dfrac{\pi^2}4$ -- соблазна не возникало?...

[EtCetera]

bot в сообщении #780674 писал(а):

1. Определите знак выражения $\sum\limits^{n-1}_{k=1}\sin\left(\cos\frac{k\pi }{n}\right)$.

$\sin\left(\cos\dfrac{(n-k)\pi}{n}\right)=-\sin\left(\cos\dfrac{k\pi}{n}\right)$, поэтому знак отсутствует.

bot в сообщении #780674 писал(а):

2. Докажите, что $\sum\limits_{k=0}^n(k+1)C_n^k=2^{n-1}(n+2)$ %$\sum\limits_{k=0}^n(-1)^{k}(k+1)C_n^k=0$

$$\sum\limits_{k=0}^n (k+1)\binom{n}{k}=\left.\left(x\left(x+1\right)^n\right)'\right|_{x=1}=\left.\left(x+1\right)^{n-1}\left(\left(n+1\right)x+1\right)\right|_{x=1}=2^{n-1}(n+2)$$

Второе аналогично, только берем $x=-1$.

(bot)

А что означает процент в записи условия?

bot в сообщении #780674 писал(а):

3. Исследуйте сходимость ряда $\sum\limits_{n=1}^\infty n!\left(\frac{a}{n}\right)^n$ при $a\in \mathbb R$.

По признаку Коши имеем

$$\lim\limits_{n\to\infty}\sqrt[n]{n!\left(\frac{a}{n}\right)^n}=\lim\limits_{n\to\infty}\sqrt[2n]{2\pi n}\cdot\frac{n}{e}\cdot\frac{a}{n}=\frac{a}{e}$$

т.е. ряд сходится при $a<e$. При $a=e$ ряд расходится, т.к. $n!\left(\frac{e}{n}\right)^n\ge\sqrt{2\pi n}$.

bot в сообщении #780674 писал(а):

5. Докажите неравенство

$$\dfrac{1}{\sqrt{n}}+\dfrac{1}{\sqrt{n+1}}+ \ldots + \dfrac{1}{\sqrt{n^2-1}}>2\left(n-\sqrt n\right)$$

$$\sum\limits_{k=n}^{n^2-1}\dfrac{1}{\sqrt{k}}>\int\limits_n^{n^2}\dfrac{dx}{\sqrt{x}}=2\left(n-\sqrt n\right)$$

[ewert]

EtCetera в сообщении #780807 писал(а):

По признаку Коши имеем

Только не по Коши, а по Даламберу: $\dfrac{b_{n+1}}{b_n}=\dfrac{a}{(1+\frac1n)^n}$. Не забывая при этом, что $(1+\frac1n)^n$ всё-таки $<e$. И ещё не забывая, что $a$ может быть и отрицательным. И вообще это совершенно стандартный учебный степенной ряд, так что непонятно.

-- Вс окт 27, 2013 14:49:13 --

bot в сообщении #780674 писал(а):

1. Положительные числа $x, y, z$ удовлетворяют равенствам $xyz=1$ и $x+y+z=\frac1x+\frac1y+\frac1z$. Найдите среднее из них.

Не понял. Ясно, что хотя бы одно из чисел равно единице -- например, $z$; но тогда два других связаны лишь равенством $xy=1$ и ничем более.

А-а, ну разве что в этом смысле среднее. Провокационная формулировка.

[ewert]

bot в сообщении #780674 писал(а):

5. Целые положительные числа $a, b , c , d$ удовлетворяют равенству $ab=cd$. Может ли число $a+b+c+d$ быть простым числом?

$a+b+c+d=(\alpha+\beta)(m+n)$, где дробь $\frac mn=\frac ac=\frac db$ несократима.

[bot]

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

Провокационная формулировка

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

-- Вс окт 27, 2013 22:06:11 --

EtCetera в сообщении #780807 писал(а):

bot в сообщении #780674
писал(а):
2. Докажите, что $\sum\limits_{k=0}^n(k+1)C_n^k=2^{n-1}(n+2)$ %$\sum\limits_{k=0}^n(-1)^{k}(k+1)C_n^k=0$

Не уследил bot при отправке сообщения, что остался запасной вариант, который после % идёт.

[EtCetera]

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

Только не по Коши, а по Даламберу: $\dfrac{b_{n+1}}{b_n}=\dfrac{a}{(1+\frac1n)^n}$.

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

И ещё не забывая, что $a$ может быть и отрицательным.

Двух слонов я и не заметил. Извиняюсь.

bot в сообщении #780674 писал(а):

2. Можно ли число 600 разложить в сумму 9 целых положительных слагаемых так, чтобы всевозможные суммы этих слагаемых, взятых не более одного раза, были различны?

$2^k$ при $k=0\dots 7$ и $600-\left(2^8-1\right)=345$. Но почему именно 600?

[ewert]

bot в сообщении #780674 писал(а):

3. Даны две непрерывные функции $f, g : [a;b] \to [a;b]$, причём $f(g(x))=g(f(x))$ при всех $x \in [a;b]$.
Множество неподвижных точек функции $f$ связно. Докажите, что $f$ и $g$ имеют общую неподвижную точку.

Всё-таки связность множества стационарных точек -- очень уж сильное требование. Благодаря ему задача сводится к следующему: если функция $g(x)$ переводит некоторый отрезок $[\alpha;\beta]$ в себя, то она имеет на этом отрезке хотя бы одну неподвижную точку. Ну имеет.

[Sonic86]

bot в сообщении #780674 писал(а):

1. На конечном множестве $G$ задана ассоциативная операция $\cdot$. Докажите что в $G$ существует идемпотент (то есть элемент $x$, удовлетворяющий тождеству $xx=x$).

Выберем $y\in G$. Рассмотрим степени $y$: $y,y^2,y^3,...$. $G$ конечно, значит найдется бесконечная возрастающая последовательность показателей $a_1,a_2,...,a_k,...$ таких, что $y^{a_1}=y^{a_k}$, $x_k:=y^{a_k-a_1}$. Тогда $x_k^2=y^{a_k-2a_1}y^{a_k}=y^{a_k-2a_1}y^{a_1}=x_k$ при $a_k-2a_1\geqslant 0$. Поскольку $\lim\limits_{k\to +\infty}a_k = +\infty$, то $k$, удовлетворяющее последнему неравенству, существует.

[ewert]

Попробуем добить.

bot в сообщении #780674 писал(а):

2. Существует ли непрерывная функция $f:\mathbb R\to\mathbb R$, удовлетворяющая тождеству

$$f(f(x))=e^{-x}\, ?$$

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

Достаточно очевидно, что единственная стационарная точка $x_0$ функции $f(x)$ -- это решение уравнения $x=e^{-x}$. И что последовательность $x_{k+1}=f(x_k)$ сходится к этой точке, начиная с любого начального приближения. Как следствие -- $f(x)>x \text{ при } x<x_0$ и $f(x)<x \text{ при } x>x_0$ (иначе сходимости не было бы).

Однако последовательность $x_{n+1}=f(f(x_n))=e^{-x_n}$ имеет одно интересное свойство: каждая следующая итерация оказывается по другую сторону от $x_0$, нежели предыдущая (притом строго по другую). Это означает, что невозможно ни одно из неравенств $f(x)<x_0 \text{ при } x<x_0$ или $f(x)>x_0 \text{ при } x>x_0$ (иначе мы в последовательности $x_{k+1}=f(x_k)$ так и оставались бы по одну сторону от $x_0$, начиная с некоторого приближения). Но и одновременно $f(x)>x_0 \text{ при } x<x_0, \quad f(x)<x_0 \text{ при } x>x_0$ также невозможно -- тогда через каждую пару итераций мы возвращались бы на прежнюю сторону от $x_0$. По совокупности это означает: как минимум или слева от $x_0$, или справа должно встречаться как $f(x)\leqslant x_0$, так и $f(x)\geqslant x_0$. И, следовательно (в силу непрерывности), должно встречаться $f(x)=x_0$. Но и это невозможно: тогда бы мы уже после следующего шага застопорились бы на $x_0$, что также запрещено.

Как-то не шибко иммер элегант, да.

[Oleg Zubelevich]

bot в сообщении #780674 писал(а):

Существует ли непрерывная функция $f:\mathbb R\to\mathbb R$, удовлетворяющая тождеству

$$f(f(x))=e^{-x}\, ?$$

Я бы предложил ТС такую задачу.
Рассмотрим непрерывное отображение $f:\mathbb{R}^m\to\mathbb{R}^m$. Известно, что отображение $g=f\circ f$ гладкое и имеет единственную неподвижную точку $x'$. Доказать, что $\det(dg(x'))$ не может быть отрицательным.

[ewert]

(Оффтоп)

"Хорошее предложение, но не для нашего климату" (с) Ф.И.