Выбрано 13 задач 
Убрать все задачи
100 гирек веса 1, 2, ..., 100 г разложили на две чаши весов так, что есть
равновесие.
Докажите, что можно убрать по две гирьки с каждой чаши так, что
равновесие не нарушится.
Имеется 100 палочек, из которых можно сложить 100-угольник.
Может ли случиться, что ни из какого меньшего числа этих палочек нельзя сложить многоугольник?
а) Найдите ГМТ, равноудаленных от двух параллельных
прямых.
б) Найдите ГМТ, равноудаленных от двух пересекающихся прямых.
Плоскость α пересекает рёбра AB, BC, CD и DA треугольной пирамиды ABCD в точках K, L, M и N соответственно. Оказалось, что двугранные углы
∠(KLA, KLM), ∠(LMB, LMN), ∠(MNC, MNK) и ∠(NKD, NKL) равны. (Через ∠(PQR, PQS) обозначается двугранный угол при ребре PQ в тетраэдре PQRS.) Докажите, что проекции вершин A, B, C и D на плоскость α лежат на одной окружности.
Какое наименьшее число клеток надо отметить на доске 15×15 так, чтобы слон с любой клетки доски бил не менее двух отмеченных клеток? (Слон бьёт и ту клетку, где стоит.)
Дан квадрат ABCD, M и N – середины сторон BC и AD. На продолжении диагонали AC за точку A взяли точку K. Отрезок KM пересекает сторону AB
в точке L. Докажите, что углы KNA и LNA равны.
В одной из вершин а) октаэдра; б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?
а) У Тани есть 4 одинаковые с виду гири, массы которых равны 1000, 1002, 1004 и 1005 г (неизвестно, где какая), и чашечные весы (показывающие, какая из двух чаш перевесила или что имеет место равенство). Может ли Таня за 4 взвешивания гарантированно определить, где какая гиря? (Следующее взвешивание выбирается по результатам прошедших.)
б) Тот же вопрос, если у весов левая чашка на 1 г легче правой, так что весы показывают равенство, если масса на левой чашке на 1 г больше, чем на правой.
Некоторый куб рассекли плоскостью так, что в сечении получился пятиугольник.
Докажите, что длина одной из сторон этого пятиугольника отличается от 1 метра по крайней мере на 20 сантиметров.
Пусть $O$ – центр описанной окружности остроугольного треугольника $ABC$, точка $M$ – середина стороны $AC$. Прямая $BO$ пересекает высоты $AA_1$ и $CC_1$ в точках $H_a$ и $H_c$ соответственно. Описанные окружности треугольников $BH_aA$ и $BH_cC$ вторично пересекаются в точке $K$. Докажите, что $K$ лежит на прямой $BM$.
На плоскости отмечена точка M, не лежащая на осях координат. По оси ординат движется точка Q, а по оси абсцисс точка P так, что угол PMQ всегда остаётся прямым. Найдите геометрическое место точек N, симметричных M относительно PQ.
Натуральное число n назовём хорошим, если каждый его натуральный делитель, увеличенный на 1, является делителем числа n + 1.
Найдите все хорошие натуральные числа.
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(a_n)$ строится следующим образом: $a_0 = 0$, $a_1 = 1$ и при $n > 1$ число $a_n$ — такое минимальное натуральное число, большее $a_{n-1}$, что среди чисел $a_0$, $a_1$, ..., $a_n$ нет трёх, образующих триплет. Докажите, что $a_{2023} \leqslant 100\,000$.
|
|
 |
Условие
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(a_n)$ строится следующим образом: $a_0 = 0$, $a_1 = 1$ и при $n > 1$ число $a_n$ — такое минимальное натуральное число, большее $a_{n-1}$, что среди чисел $a_0$, $a_1$, ..., $a_n$ нет трёх, образующих триплет. Докажите, что $a_{2023} \leqslant 100\,000$.
Решение
Обозначим через $b(n)$ двоичную запись числа $n$; например, $b(13) = 1101$. Обозначим число, троичная запись которого совпадает с $b(n)$, через $b(n)_3$; например, $b(13)_3 = 1101_3 = 1 + 9 + 27 = 37$. Докажем индукцией по $n$, что $a_n = b(n)_3$.
База индукции ($n\leq 1$) дана в определении. Переход: пусть для всех $i < n$ троичная запись числа $a_i$ совпадает с $b(i)$. Необходимо доказать, что, во-первых, число $b(n)_3$ не образует триплета с какими-нибудь $a_i$ и $a_j$ для $i < j < n$ и, во-вторых, никакое меньшее число не удовлетворяет этому условию.
Предположим, что найдутся такие числа $i$ и $j$, что $0\leq i < j < n$ и $b(i)_3 + b(n)_3 = 2\cdot b(j)_3$. Заметим, что при сложении чисел $b(i)_3$ и $b(n)_3$ в троичной системе счисления не возникает переходов через разряд, поэтому если в результате получилось число $2\cdot b(j)_3$, то на всех позициях, где в строке $b(j)$ стоит единица, в обеих строках $b(i)$ и $b(n)$ также стоят единицы, а на всех остальных позициях в этих строках стоят нули. Таким образом, $b(i) = b(j) = b(n)$, из чего следует, что $i = j = n$. Противоречие.
Докажем теперь, что любое число, меньшее $b(n)_3$ (и большее $a_{n-1}$), образует триплет с какими-нибудь $a_i$ и $a_j$. Рассмотрим произвольное число $x$, удовлетворяющее неравенству $b(n-1)_3 < x < b(n)_3$. Поскольку $b(n-1)_3$ и $b(n)_3$ — это два соседних числа, чья троичная запись состоит из нулей и единиц, в троичной записи числа $x$ есть двойка.
Пусть троичная запись числа $x$ — это строка $s_n$. Построим строки $s_i$ и $s_j$, состоящие из нулей и единиц и имеющие такую же длину, что и $s_n$, по следующему принципу: единицы в $s_i$ стоят ровно на тех позициях, где в строке $s_n$ стоят единицы; единицы в $s_j$ стоят ровно на тех позициях, где в строке $s_n$ стоят ненулевые цифры. Возьмём в качестве $i$ число с двоичной записью $s_i$, а в качестве $j$ — число с двоичной записью $s_j$. Пусть $d_i$, $d_j$ и $d_n$ — цифры в какой-то позиции строк $s_i$, $s_j$ и $s_n$ соответственно. Тогда заметим, что, во-первых, $d_i\leq d_j\leq d_n$, а во-вторых, $2d_j = d_i + d_n$. Более того, в тех позициях, где в строке $s_n$ стоит двойка, выполняется цепочка строгих неравенств $d_i < d_j < d_n$. Значит, $i < j < n$, и числа $(a_i, a_j, x)$ образуют триплет, что и требовалось доказать.
Поскольку $2023 < 2048 = 2^{11}$, имеем, что в троичной записи числа $a_{2023}$ не больше $11$ цифр, ни одна из которых не превосходит $1$. Значит, \begin{align*} a_{2023} & \leq 3^0 + 3^1 + \ldots + 3^{10} = \frac{3^{11} - 1}{2} \leq \frac{243^2\cdot 3}{2} \leq {} \\ & \leq \frac{250^2\cdot 3}{2} = 62\,500\mkern2mu\cdot \frac{3}{2} < 66\,666\mkern2mu\cdot\frac{3}{2} < 100\,000 . \end{align*}
Комментарий. На самом деле $a_{2023} = 88\,465$.
