М605. Задача о преобразовании плоскости

Условие

На плоскости отмечены $2n + 1$ различных точек. Занумеруем их числами $1, 2, \ldots, 2n + 1$ и рассмотрим следующее преобразование $R$ плоскости: сначала делается симметрия относительно первой точки, затем относительно второй и т. д. — до $\left(2n + 1\right)$-й точки.

а) Покажите, что y этого преобразования $R$ есть единственная «неподвижная точка» (точка, которая отображается в себя).

Рассмотрим всевозможные способы нумерации наших $2n + 1$ точек (числами $1, 2, \ldots, 2n + 1$). Каждой такой нумерации соответствует свое преобразование плоскости $R$ и своя неподвижная точка. Пусть $F$ — множество неподвижных точек всех этих преобразований.

б) Укажите множество $F$ для $n = 1$.

в) Какое максимальное и какое минимальное количество точек может содержать множество $F$ при каждом $n = 2, 3, \ldots$

Решение

Фиксируем произвольную систему координат.

Пусть точки $A\left(x; y\right)$ и $A^*\left(x^*; y^*\right)$ симметричны относительно точки $A’\left(x’; y’\right)$. Тогда $x’ = \frac{\left(x + x^*\right)}{2}, y’ = \frac{\left(y + y^*\right)}{2},$ откуда $$x^* = 2x’ — x, y^* = 2y’ — y.$$

Таким образом, точка с координатами $\left(x; y\right)$ при симметрии относительно точки с координатами $\left(x’; y’\right)$ переходит в точку с координатами $\left(2x’ — x; 2y’ — y\right)$.

Поэтому при нашем преобразовании $R$ точка с координатами $\left(x; y\right)$ перейдет в точку с координатами $\left(-x + 2x_1 — 2x_2 + \cdots + 2x_{2n + 1}; -y + 2y_1 — 2y_2 + \cdots + 2y_{2n + 1}\right),$ где $\left(x_i; y_i\right)$ — координаты $i$-й из заданных $2n + 1$ точек.

a) Для неподвижной точки $\left(x; y\right)$ преобразования $R$ эти координаты определяются однозначно из условия $$ \begin{cases}-x + 2x_1 — 2x_2 + \cdots + 2x_{2n + 1} = x \\ -y + 2y_1 — 2y_2 + \cdots + 2y_{2n + 1} = y\end{cases}$$ и равны $\left(x_1 — x_2 + \cdots — x_{2n} + x_{2n + 1}; y_1 — y_2 + \cdots — y_{2n} + y_{2n + 1}\right)$ или $$\left(\sum_{i = 1}^{2n + 1} \left(-1\right)^{i — 1} x_i; \sum_{i = 1}^{2n + 1} \left(-1\right)^{i — 1} y_i\right) \tag{*}$$ Утверждение a) доказано.

б) Пусть сначала данные точки $X_1, X_2, X_3$ не лежат на одной прямой. Если точка $A_1$ после симметрии относительно точек $X_1, X_2, X_3$ отобразилась в себя (см. рисунок), то $X_1, X_2, X_3$ — середины отрезков $A_1A_2, A_2A_3, A_3A_1$, где $A_2 = SX_1\left(A_1\right)$, $A_3 = SX_2\left(A_2\right)$. Значит, $\left[A_1A_2\right]$, $\left[A_2A_3\right]$, $\left[A_3A_1\right]$ — медианы треугольника $A_1A_2A_3$, так что точки $A_1, A_2, A_3$ можно получить из точек $X_1, X_2, X_3$ гомотетией с центром в центре тяжести $O$ треугольника $X_1X_2X_3$ и коэффициентом $(—2)$. Этим положение точек $A_i \left(i = 1, 2, 3\right)$ определяется однозначно. С другой стороны, каждая точка $A_i$ при соответствующей композиции симметрий относительно точек $X_i$, отображается в себя (например, $SX_2\left(SX_1\left(SX_3\left(A_3\right)\right)\right) = A_3$). Поэтому множество $F$ — это три точки, получающиеся из данных точек $X_1, X_2, X_3$ гомотетией с центром $O$ и коэффициентом $(-2)$. Легко видеть, что, если данные точки $X_1, X_2, X_3$ лежат на прямой, ответ получается, в разумном смысле, тот же.

в) Глядя на выражение $(*)$, нетрудно сообразить, что в множестве $F$ точек не больше, чем число способов выбрать из $2n + 1$ данных точек те $n$ точек, перед абсциссами которых в выражении $(*)$ будет стоять знак «минус», то есть не больше, чем $C^n_{2n + 1}$. Очевидно, эта оценка точна (возьмите, например, $2n + 1$ точек на одной прямой с целыми координатами $1, 2, 2^2, \ldots, 2^{2n}$).

Оценим теперь число неподвижных точек снизу. Спроектируем данные $2n + 1$ точек на прямую так, чтобы никакие две точки не попали в одну. На этой прямой введем координаты и перенумеруем точки в порядке возрастания координат: $x_1 < x_2 < \ldots < x_{2n + 1}$. Поставим $n$ минусов перед первыми $n$ числами и рассмотрим сумму $- x_1 — x_2 — \cdots — x_n + x_{n + 1} + \cdots + x_{2n + 1}$: она будет соответствовать некоторой неподвижной точке из нашего множества $F$. Далее произведем следующую операцию: выберем пару чисел $x_i$ и $x_{i + 1}$ таких, что перед $x_i$ стоит минус, а перед $x_{i + 1}$ — плюс, и поменяем у них знаки (на первом шаге, очевидно, $i = n$). Каждая такая операция приводит к сумме, соответствующей неподвижной точке из множества $F$, причем, поскольку после каждой такой операции сумма уменьшатся, все эти неподвижные точки различны. Всего таких операций (вне зависимости от их порядка) мы можем произвести $n\left(n + 1\right)$, что уже даст нам $n\left(n + 1\right) + 1$ неподвижных точек. Значит, в $F$ точек не меньше $n\left(n + 1\right) + 1$. Ровно столько неподвижных точек получится, если, например, снова взять $2n + 1$ точек на прямой с целыми координатами $-n, -\left(n — 1\right), \ldots, -1, 0, 1, 2, \ldots, n — 1, n$. При всевозможных способах расстановки $n$ «минусов» перед некоторыми из них максимальное значение суммы этих чисел равно $2 \cdot \left(1 + 2 + \cdots + n\right) = n(n + 1)$, минимальное значение равно $-n\left(n + 1\right)$, причем сумма может принимать любое четное значение между числами $-n\left(n + 1\right)$ и $n\left(n + 1\right)$ — всего $n\left(n + 1\right) + 1$ значений.

И. Клумова, А. Талалай

М1605 О поиске нужной тройки

Задача из журнала «Квант» (1997, №4)

Условие

Имеются N карточек, на которых написаны различные(неизвестные) числа. Они расположены на столе по кругу числами вниз. Надо найти три какие-нибудь лежащие рядом карточки такие, что число, написанное на средней карточке, больше, чем на каждой из двух соседних. При этом разрешается перевернуть последовательно не более k карточек. Докажите, что это возможно, если:

а) N=5, k=4; б)N=76, k=10; в)N=199, k=12 ;

Решение

а) «Откроем» среди 5 чисел, расположенных по окружности, два числа a < b, стоящих на расстоянии 2 друг от друга, и еще одно, соседнее с большим из них — c. Из соображений симметрии, можно считать, что c <b> 79, f_{12}=223 > 199, это даст решения задач б) и в). Для этого докажем сначала индукцией по k, что в рядуa, ... ,b, ... ,c

из f_k + f_{k-1}+1= f_{k+1} + 1 чисел, где известны a, b, c, причем d - наибольшее и находится от a и c на расстоянии f_{k-1} и f_{k-2}, можно найти нужную тройку за k-1 попытку. Для k = 2(для ряда из четырех чисел a, b, ., c) это очевидно. Пусть вплоть до некоторого значения k-1 то доказано. Рассмотрим данный ряд и «откроем» число d, находящееся на расстояниях f_{k-1} от a и f_{k-2} от b:

a, ... , d, ..., b, ... , c

Если d > b, то мы можем применить предположение индукции к f_k + 1 числам a, ... , d , ... , b, а если d < b — то к числам d, ... , b, ... , c : за k-2 попытки среди них найдется нужная тройка.

Теперь среди f_k = f_{k-1} + f_{k-2} = 2f_{k-2} + f_{k-3} чисел по окружности достаточно «открыть» два числа a < b на расстоянии f_{k-2} и число c, находящееся на расстоянии f_{k-2} от a и f_{k-3} от b. По соображениям симметрии, можно считать, что b > c. По доказанному выше, среди идущих подряд f_{k-2} + f_{k-3} + 1 = f_{k-1} + 1 чисел a, ... , b, ... , c за k-3 попытки можно найти нужную тройку.

В. Протасов, А. Заславский

qunt