В $n$-элементной последовательности $(x_1, x_2, \ldots, x_n)$ каждый элемент равен 0 или 1. Назовем такую последовательность бинарной последовательностью длины $n$. Пусть $a_n$ равно равно количеству бинарных последовательностей длины $n,$ не содержащих трёх последовательных членов равных 0, 1, 0 (в этом порядке). Пусть $b_n$ равно количеству бинарных последовательностей длины $n,$ не содержащих четырёх последовательных членов равных 0, 0, 1, 1 или 1, 1, 0, 0 (в этом порядке). Докажите, что $b_{n+1} = 2a_n$ для всех положительных целых чисел $n.$ |  |
Дан треугольник $ABC.$ Докажите, что найдётся прямая $l$ (в плоскости треугольника $ABC$) такая, что площадь пересечения треугольника $ABC$ и треугольника $A'B'C',$ симметричного $ABC$ относительно $l,$ составляет более чем $\frac{2}{3}$ площади треугольника $ABC$. | |
Для непустого множества действительных чисел $S$ пусть $\sigma(S)$ обозначает сумму элементов $S$. Дано множество $A,$ состоящее из $n$ положительных целых чисел. Рассмотрим набор всех различных $\sigma(S),$ получающихся при их вычислении для всех $S,$ являющихся непустыми подмножествами $A$. Докажите, что этот набор сумм может быть разбит на $n$ классов так, что в каждом классе отношение большей суммы к меньшей не превосходит 2. | |
Докажите, что среднее арифметическое чисел $n\sin n^{\circ}\; (n = 2,4,6,\ldots,180)$ равно $ctg 1^\circ$. | |
Предположим, что о каждой паре людей из некоторого сообщества можно сказать, что она состоит из друзей или врагов. Каждый член дружественной пары дружит с другим членом этой пары, а каждый член враждебной пары враждует с другим членом этой пары. Рассмотрим сообщество из $n$ людей, в котором $q$ пар друзей и в котором в любой группе, состоящей из трех членов сообщества, есть по крайней мере одна пара врагов. Докажите, что есть по крайней мере один член сообщества такой, что среди его врагов есть $\, q(1 - 4q/n^2)$ или меньше пар друзей. | |
Последовательность $q_1,q_2,\ldots,$ состоящая из целых чисел, удовлетворяет двум условиям: (a) $m - n$ делит $q_m - q_n$ при $m>n \geq 0$ (b) Существует многочлен $P$ такой, что $|q_n| < P(n)$ для всех $n.$ Докажите, что существует многочлен $Q$ такой, что $q_n = Q(n)$ для всех $n.$ | |
Дан неравнобедренный, непрямоугольный треугольник $ABC.$ Пусть $O$ обозначает центр описанной окружности и пусть $A_1, \, B_1,$ и $C_1$ будут соответственно серединами сторон $BC, \, CA$ и $AB.$ Точка $A_2$ лежит на луче $OA_1,$ причем $\triangle OAA_1$ подобен $\triangle OA_2A$. Аналогично задаются точки $B_2$ и $C_2,$ которые соответственно лежат на лучах $OB_1$ и $OC_1.$ Докажите, что прямые $AA_2, \, BB_2$ и $CC_2$ проходят через одну точку. | |
Пусть $p$ --- нечётное простое число. О последовательности $(a_n)_{n \geq 0}$ известно, что $a_0 = 0,$ $a_1 = 1,$ \ldots, $a_{p-2} = p-2$ и что, для всех $n \geq p-1,$ $a_n$ --- наименьшее положительное целое число, не образующее арифметическую прогрессию длины $p$ с любыми предыдущими членами последовательности. Докажите, что, для всех $n,$ $a_n$ --- число, получаемое при записи $n$ в системе счисления с основанием $p-1$ и чтением результата в системе счисления с основанием $p.$ | |
У триголятора есть только кнопки $\sin,$ $\cos,$ $\tan,$ $\sin^{-1},$ $\cos^{-1},$ и $\tan^{-1}.$ На дисплее изначально отображается число 0. Дано положительное рациональное число $q.$ Покажите, что с помощью конечного количества нажатий на кнопки можно получить $q$ на дисплее. Предполагается, что все вычисления выполняются точно и все функции вычисляются для аргументов, выраженных в радианах. | |
Пусть $|U|, \sigma(U)$ и $\pi(U)$ обозначают соответственно количество, сумму и произведение элементов конечного множества положительных целых чисел $U.$ (Если $U$ является пустым множеством, то считаем что $|U| = 0, \sigma(U) = 0, \pi(U) = 1.$) Пусть $S$ --- конечное множество положительных целых чисел. Как обычно, пусть $C_n^k$ обозначает $\frac{n!}{k! \, (n-k)!}.$ Докажите, что $\sum_{U \subseteq S} (-1)^{|U|} C_{m - \sigma(U)}^{|S|} = \pi(S)$ для всех целых чисел $m \geq \sigma(S).$ | |
Последовательность положительных действительных чисел $a_1, a_2, a_3, \ldots$ удовлетворяет неравенству $\sum_{j = 1}^n a_j \geq \sqrt {n}$ для всех $n \geq 1.$ Докажите, что для всех $n \geq 1$ $\sum_{j = 1}^n a_j^2 > \frac {1}{4} \left( 1 + \frac {1}{2} + \cdots + \frac {1}{n} \right).$ | |
