Выбрано 2 задачи 
Убрать все задачи
Будем называть точку плоскости узлом, если обе её координаты – целые числа. Внутри некоторого треугольника с вершинами в узлах лежит ровно два узла (возможно, какие-то еще узлы лежат на его сторонах). Докажите, что прямая, проходящая через эти два узла, либо проходит через одну из вершин треугольника, либо параллельна одной из его сторон.
Докажите, что растяжение плоскости является аффинным преобразованием.
|
|
 |
Условие
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(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$.
