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

[bot]

1 тур (12 октября)

1 курс.

1. Определить все значения параметра $a$, при каждом из которых уравнение \\ $\cos^4 2x - \cos x= a^2 + a $ имеет единственное решение в промежутке $ [0; 2\pi).$

2. Доказать, что площадь многоугольника, вершины которого имеют рациональные координаты, является числом рациональным.

3. Последовательность $x_n, n \geqslant 0$ задана рекуррентностью $x_{n+2}=|x_{n+1}-x_{n-1}|, \ n \geqslant 1$ с произвольными целыми $x_0, x_1, x_2$. Докажите, что существует номер, начиная с которого последовательность становится периодической.

4. Найти все натуральные $n$, для которых $n!$ делится на $n^2$.

5. Найдите наименьший квадрат, который можно сложить из $10$ различных прямоугольников с целочисленными сторонами.


2-4 курсы


1. Пусть $A$ и $B$ - произвольные квадратные матрицы втоого порядка. Докажите, что матрица $(AB-BA)^2$ перестановочна с любой квадратной матрицей второго порядка.

2. Вычислить интеграл $\displaystyle \int\limits_{- \pi}^{\pi} \frac{\cos x\,dx}{1+e^x}$.

3. Последовательность $x_n, n \geqslant 0$ задана рекуррентностью $x_{n+2}=|x_{n+1}-x_{n-1}|, \ n \geqslant 1$ с произвольными целыми $x_0, x_1, x_2$. Докажите, что существует номер, начиная с которого последовательность становится периодической.

4. Докажите, что знакопостоянный ряд $\sum\limits_{n=1}^\infty a_n$, все члены которого отличны от $-1$, сходится тогда и только тогда, когда сходится ряд $\sum\limits_{n=1}^\infty \frac{a_n}{1+a_n}$.
Покажите на примерах, что при нарушении знакопостоянства первого ряда любой из них может сходиться, а другой расходиться.

5. Пусть $p=6k+1$. Докажите, что при любых целых $a,b$,
хотя бы одно из которых отлично от нуля, число $(a+b)^p-a^p-b^p$ делится на $(a^2+ab+b^2)^2.$

[nnosipov]

bot
в 3-й задаче для 2-4 курсов недопечатано условие. Оно такое же, как и в соответствующей задаче для 1 курса?

[bot]

Да, такое же

(Оффтоп)

- у меня экран с длинным текстом в конце окошечка дёргается, приходится наощуп писать.

Спасибо, исправил.

[Sonic86]

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

5. Пусть $p=6k+1$. Докажите, что при любых целых $a,b$,
хотя бы одно из которых отлично от нуля, число $(a+b)^p-a^p-b^p$ делится на $(a^2+ab+b^2)^2.$

В силу однородности достаточно доказать, что $\Phi_p: (x^2+x+1)^2\mid (x+1)^p-x^p-1$. Докажем это по индукции.
При $p=1$ соотношение верно.
Пусть $\Phi_p$ верно, докажем из него $\Phi_{p+6}$:
$(x+1)^{p+6}-x^{p+6}-1\equiv 0\pmod{(x+1)^p-x^p-1, (x^2+x+1)^2}\Leftarrow$
$(x+1)^{p+6}-x^{p+6}-1-x^6((x+1)^p-x^p-1)\equiv 0\pmod{(x^2+x+1)^2}\Lefttarrow$
$(x+1)^p((x+1)^6-x^6)+(x^6-1)\equiv 0\pmod{(x^2+x+1)^2}$
В левой части $(x+1)^6-x^6$ и $x^6-1$ делятся на $x^2+x+1$. Делим, а дальше $(x+1)^p\equiv -x^2 (x^2+x+1)$, и просто проверяем.
В Кванте или у кого-то есть доказательство лучше?

[bot]

Sonic86 в сообщении #917967 писал(а):

$(x^2+x+1)^2\mid (x+1)^p-x^p-1$

Для этого достаточно проверить, что первообразный корень 3-й степени из единицы является двукратным корнем делимого. Задача, уверен, не оригинальна, хотя ни в Кванте ни в других источниках не рылся.

[nnosipov]

Sonic86 в сообщении #917967 писал(а):

В Кванте или у кого-то есть доказательство лучше?

Я брал корень $\zeta$ многочлена $x^2+x+1$ и проверял равенства $f(\zeta)=f'(\zeta)=0$, где $f(x)=(x+1)^p-x^p-1$. По-моему, всё это одинаково несложно.

-- Вс окт 12, 2014 18:54:44 --

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

хотя ни в Кванте ни в других источниках не рылся

Здесь этот сюжет несколько раз обсуждался. В "Кванте" это задача М2173.

[Sonic86]

(Оффтоп)

nnosipov в сообщении #917979 писал(а):

проверял равенства $f(\zeta)=f'(\zeta)=0$

Блин, стандартную технику я забыл значит опять.

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

2. Доказать, что площадь многоугольника, вершины которого имеют рациональные координаты, является числом рациональным.

Достаточно доказать утверждение для выпуклых многоугольников с $\mathbb{Q}$-координатами, поскольку произвольный $\mathbb{Q}$-многоугольник представим в виде разности его $\mathbb{Q}$-выпуклой оболочки и других $\mathbb{Q}$-многоугольников, которые можно разбить на выпуклые $\mathbb{Q}$-треугольники.
Проведем в $\mathbb{Q}$-многоугольнике через все его вершины вертикальные и горизонтальные прямые. Они разобьют $\mathbb{Q}$-многоугольник на $\mathbb{Q}$-прямоугольники и $\mathbb{Q}$-прямоугольные трапеции, у которых стороны параллельны осям координат. В силу последнего их площади рациональны. Значит площадь $\mathbb{Q}$-многоугольника рациональна

-- Вс окт 12, 2014 15:12:28 --

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

4. Докажите, что знакопостоянный ряд $\sum\limits_{n=1}^\infty a_n$, все члены которого отличны от $-1$, сходится тогда и только тогда, когда сходится ряд $\sum\limits_{n=1}^\infty \frac{a_n}{1+a_n}$.

Это равносильно тому, что для $a_n>0, e=\pm 1$ если один из рядов $\sum\limits_{n=1}^\infty a_n, \sum\limits_{n=1}^\infty \frac{a_n}{1+e a_n}$ сходится, то и второй сходится.
Рассматривать сходимость достаточно с некоторого номера $r$
Если $a_n>0$, то $\sum\limits_{n=r}^\infty \frac{a_n}{1+ea_n}=\sum\limits_{n=r}^\infty a_n-e\sum\limits_{n=r}^\infty \frac{a_n^2}{1+ea_n}$. Будем считать, что $r$ настолько велико, что $a_n<1$ и $a_n<1+ea_n$ при $n\geqslant r$ (оно существует, т.к. $\lim\limits_{n\to\infty} a_n = 0$). Тогда $\frac{a_n^2}{1+ea_n} < \frac{a_n} {1+ea_n}$ и $\frac{a_n^2}{1+ea_n}<a_n$. Значит, если хотя бы один из данных изначально рядов сходится, то сходится и ряд $\sum\limits_{n=r}^\infty \frac{a_n^2}{1+ea_n}$, а значит сходится и второй ряд.

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

4. Найти все натуральные $n$, для которых $n!$ делится на $n^2$.

Это теорема Вильсона и ее обращение: $n$ либо простое, либо $4$, либо остальные.

[Shadow]

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

4. Найти все натуральные $n$, для которых $n!$ делится на $n^2$.

$n \mid (n-1)!$. При n $\in \mathbb{P}$ понятно, решений нет. Если $n$ можно разложить на два различных, отличных от 1 множителя, то они будут присутствовать как различные множители в $(n-1)!$. Составное $n$ нельзя разложить на два различных, отличных от 1 множителя, только если $n=p^2$
В $(n-1)!$ присутствуют множители $p,2p$, когда $n-1\ge 2p$. Тоесть, когда $p^2-1 \ge 2p$

Ответ: все составные $n$ за исключением 4.

[ex-math]

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

2. Вычислить интеграл $\displaystyle \int\limits_{- \pi}^{\pi} \frac{\cos x\,dx}{1+e^x}$.

Интеграл равен нулю. Заменяя $y=-x$, получим $\displaystyle \int\limits_{- \pi}^{\pi} \frac{\cos y\,dy}{1+e^{-y}}$, а сложив его с исходным придем к интегралу от косинуса по периоду.

[ewert]

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

2. Доказать, что площадь многоугольника, вершины которого имеют рациональные координаты, является числом рациональным.

Какая-то странная задача. Известно же, что для треугольника есть явная формула через координаты.

[Shadow]

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

Какая-то странная задача. Известно же, что для треугольника есть явная формула через координаты.

Думаю, можно и без явной формулы. (я например ее не помню, хотя наверное могу вывести). Если "вписать" наш треугольник в прямоугольник, стороны которого паралельны осей координат, то его площадь выражается как разность площади прямоугольника (с рациональными сторонами) и площадей прямоугольных треугольников (треугольника) с рациональными катетами.

[ewert]

Shadow в сообщении #918217 писал(а):

Думаю, можно и без явной формулы. (я например ее не помню, хотя наверное могу вывести).

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

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

[EtCetera]

А мне почему-то сразу пришла на ум формула Пика...

[iifat]

Sonic86 в сообщении #918056 писал(а):

произвольный $\mathbb{Q}$-многоугольник представим в виде разности его $\mathbb{Q}$-выпуклой оболочки и других $\mathbb{Q}$-многоугольников

Самопересекающиеся сюда подпадают? Или не подпадают под условия задачи? Можно, конечно, добавить точки пересечения сторон, они, навскидку (тоже лень формулу выводить), также с рациональными координатами.

[mihiv]

2.1 Пусть матрица $Q=AB-BA$. По теореме Гамильтона-Кэли: $Q^2=Q(TrQ)-I(detQ), TrQ=a_{il}b_{li}-b_{il}a_{li}=0$ (по повторяющимся индексам суммирование). Следовательно, $Q^2$ кратна единичной матрице.