Решения задач М200, М208—М210; Ф218—Ф222

36

Решения задач
M200, M208-M210; Ф218-Ф222

M200. a) На рисунке 1 изображены шесть точек, которые лежат по три на четырех прямых. Доказите, что можно 24 разными способами отобразить это множество из шести точек на себя mak, чтобы каждый три точки лежат одной прямой, отображались в три точки, также лежащие на одной прямой.

6. На рисунке 2 две точки лежат по три на четырех прямых, причем через каждую точку проходит по три максимальным значением «конфигурацию Паскала». Сколькими способами можно множество наших девятых точки отобразить на себя mak, чтобы каждый трейка точка, лежащая на одной из девятых прямых, отображалась на同一 точке.

Рис. 1.

Рис. 2.

Рис. 3.

троичку точки, которая лежит на некомторой прямой из нашей конфигурации?

b) Тот же вопрос для конфигурации Дезарга (из десяти точки и десяти прямых), изображенной на рисунке 3.

В пунктах 6) и в) задачи значительное решение найти ответ, чем его обосновать.

Ответ можно получить так. Изовем треугольник тройки точки, не лежащих на одной прямой и таких, что каждый две из них лежат на одной прямой *), принадлежащей разумется, нашей конфигурации. Легко заметить, что если указано, какая точка переходит в каждой вершину данного треугольника (эти три точки тоже должны образовать треугольник), то положение всех остальных точки благодарна нашему условия — три точки, лежащие на одной прямой, переходит в три точки, лежащие на одной прямой, — определяется однозначно во всех трех случаях: a), 6), в).

Разберем для примера случай в). Пусть при отображении точки i, j, k перешли в точки 1, 2 и 3 соответственно. Тогда в точку 4 должна перейти та точка l, которая соединена прямыми с каждой из точки i, j, k, — две точки, лежащие на прямой, должны перейти в две точки, лежащие на прямой, — а в точки 5, 6, . . . , 10 должны перейти третий точки, лежащие на прямых, проходящих через пары точки i, j, k, l.

Позному в случае a) действительно есть 24 разных отображения: в первую вершину выделенного треугольника можно отобразить любую из шести точки, во вторую — любую из четырех точки, лежащих с ней на одной прямой, а точка, перехождения в третью вершину, определяется однозначно. Всего 6·4=24 отображения. Аналогично, в пунктах 6) и в) ответы: 9·6·2=108 и 10·6·2=120 (здесть в третью вершину треугольника может перейти не одна, а две точки). Однако обосновать наши подсчеты не просто: производа их, мы пользовались «равноправим» всех треугольников. Например, могло оказаться, что точки l, c которой соединены прямыми точки i, j, k, вообще нет или что таких точки две. Хотя это равноправие, по-видимому, имеется, его все же нужно доказать. Разумеется, это можно сделать «в люб», взяв в случае a) 24 треугольника, в случае b) 108 треугольников, а в случае c) 120 треугольников (мы различаем треугольники с разным порядком вершин). Но можно поступить и по-другому. Поскольку для описания наших конфигураций существует только, какие точки лежат на данной прямой и какие прямые проходят через данной точку, — именно эти сведения необходимо и достаточно для того, чтобы изучать отображения, — можно задавать наши конфигурации с помощью модели: указыть на

*) Порядок точки, входящих в трейку, существует.

37

бор «прямы», «точек» и указыть, какие точки и прямые инцидентины. Точка i и прямая j инцидентины, если точка i лежит на прямой j или, что то же самое, прямая j проходит через точку i. На рисунке 4 приведено несколько моделей одной и той же конфигурации.

Мы построим для каждой из конфигураций a), 6), в) такие модели, для которых равноправные треугольников будут очевидным.

Пункт a). Рассмотрим tetraэдр — правильную треугольную парамиду — и наозем прямыми его вершины, а точками — ребра. Скажем, что точка i инцидентина прямой j, если вершина j инцидентина ребру i. Проверьте, что получилось модель конфигурации пункта a). Треугольникам в этой модели отвечают три ребра, приложающие к одной границе, а нашим отображением — повороты и симметрины tetraэдра. Эти преобразования показаны на рисунке 5. Проверьте, что они переводят три точки, лежащие на одной прямой, в три точки, лежащие на одной прямой. В этой модели равноправные всех треугольников очень удобно.

Конфигурация Паскала. Модель конфигурации Паскала будет несколько более замыслованой. Рассмотрим сетку из правильных треугольников, образованную третья семействами параллельных прямых (см. рис. 6). Изготовим «точки» и «прямы» из прямых и узлов этой сетки следующим образом. Обведним все параллельные прямые через три в одну «прямую» и, аналогично, все узлы, находящиеся на прямых, через три объединим в одну «точку». На рисунке 6 узлы, входящие в одну «точку», занутерованы одинаково, а прямые, входящие в одну «прямую», имеют один и тот же цвет. «Точка» и «пряма» инцидентины, если инцидентины составляющие их узлы и прямые.

У разженее. Убедитесь, что получилась модель конфигурации Паскала.

Треугольник в модели отвечает набор треугольников, изображенный на рисунке 7. Легко убедиться, что повороты, параллельные переносы и симметрины плоскости, переводящие сетку в себя, являются допустимыми *) отображениями. Поэтому равноправные всех треугольников очень полезно — любой треугольник можно перевести в любой другой с помощью допустимого отображения.

У разженее. Докажите, что другие допустимых отображений нет.

Конфигурация Дезарга. Конфигурацию Дезарга мы представим следующим образом. Возьмем tetraэдр и отметим середины его ребер (см. рис. 8). Точка наозем вершины tetraэдра и середины его ребер, а прямыми — его ребра и середины ребер, лежащих в одной границе. Примой-ребру принадлежат лежащие на нем вершины и его середина.

*) Так для краткости мы будем называть отображения, удовлетворяющие условиям задачи.

38

Рис. 9.

У пряженее. Убедитесь, что получалась модель конфигурации Дезарга.

Какие тройки точек нашей модели являются треугольниками? Это вершины, лежащие в одной грани, или вершина и середины прилегающих к ней ребер, или середины ребер, прилегающих к одной вершине (см. рис. 9).

Хотя с точки зрения общих преобразований tetrahedra — поворотов и симметрии (см. рис. 5) — эти треугольники не равноправны, достаточно добавить еще одно преобразование $T$ (оно показано на рисунке 10), чтобы убедиться в равноправности всех треугольников и тем самым в правильности ответа.

У пряженее. Убедитесь, что повторы, симметрины и отображение $T$ являются допустимыми отображениями. Укажите все допустимые отображения.

Задача решения.

В заключение еще несколько вопросов для самостоятельного продумывания. Сколько существует допустимых отображений наших конфигураций, оставляющих неподвижными:

a) данную точку;
b) данную пару точек;
b) данную прямую (то есть отображенный, переставляющих точки, лежащие на данной прямой);
г) данную пару прямых и т.п.

M208. Известно, что разность между наибольшим и наименьшим из вещественных чисел

$$x_1, x_2, x_3, \dots, x_{10}$$

правна 1. Какой:
a) наибольший;
b) наименьший
— может быть разность между наибольшим и наименьшим из 10 чисел

$$x_1, \frac{x_1+x_2}{2}, \frac{x_1+x_2+x_3}{3}, \dots, \frac{x_1+x_2+\cdots+x_{10}}{10}$$

Каков будет ответ, если чисел не 10, а n?

Будем решать задачу сразу для $n$ чисел. Сделаем несколько предварительных замечаний.

Обозначим через $y_k$ число $\frac{x_1+x_2+\cdots+x_k}{k}$, где $k=1, 2, \dots, n$. Если прибавить ко всем $x_i$ неокоторое число $a$, то вместо чисел $y_i$ мы получим числа $y_i+a$. Максимальные разности для чисел $y_i$ и для чисел $y_i+a$ совпадают. Поэтому от набора $\{x_i\}$ с помощью подхождения выбора $a$ можно перейти к таким набору $\{x_i'\}$, что все $x_i' \geq 0$, наименьшие $x_i$ равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа $x_i$ на $1-x_i$, то $y_i$ заменяется на $1-y_i$. Следовательно, от набора $\{x_i\}$ можно перейти к набору $\{1-x_i\}$: максимальные разности между числами $y_i$ и числами $1-y_i$ одинаковы.

Решим теперь задачу a). Пусть $y_k$ — наименьшее, а $y_l$ — наибольшее из чисел $\{y_i\}$. Если $k < l$, то

$$y_l - y_k = \frac{ky_k}{l} + \frac{x_{k+1}+\cdots+x_l}{l} - y_k = \frac{x_{k+1}+\cdots+x_l}{l} - \frac{l-k}{l} y_k \leq \frac{x_{k+1}+\cdots+x_l}{l} \leq \frac{l-k}{l} = 1 - \frac{k}{l} \leq 1 - \frac{1}{n}.$$

Если же $l > k$, то $y_l - y_k = \frac{k-l}{k} y_l - \frac{y_{l+1}+\cdots+y_k}{k} \leq 1 - \frac{l}{k} \leq 1 - \frac{1}{n}$. Следовательно, максимальная разность не больше 1 – $\frac{1}{n}$. Набор с такой разностью легко указыть: $x_1 = 0, x_2 = x_3 = \dots = x_n = 1$.

Перейдем к решению задачи 6). Оценим, чем равна максимальная разность, если в наборе $\{x_i\}$ $x_k = 1, x_l = 0$. Будем считать, что $k < l$ (если это не так, то от набора $\{x_i\}$ перейдем к набору $\{1-x_i\}$).

Если $k = 1$, то разность не меньше $\frac{1}{n}$.

Действительно, тогда $y_1 = 1$, а $y_n = \frac{x_1+x_2+\cdots+x_n}{n} \leq \frac{n-1}{n}$, поскольку все $x_i < 1$, а один из них равен нулю. Пусть $\Delta_1 = y_k - y_{k-1} = \frac{1}{k-1} - \frac{y_k}{k-1}, \Delta_2 = y_{l-1} - y_l = \frac{y_{l-1}}{l}$, и если $y_k \leq y_{l-1}$, то $\Delta_2 \geq \frac{y_k}{l}$.

39

Наибольшие из чисел $\Delta_1$ и $\Delta_2$ не меньше $\frac{1}{k+l-1}$, поскольку $1 \leqslant (k-1)\Delta_1 + l\Delta_2 \leqslant (k+l-1)M$, где $M = \max(\Delta_1, \Delta_2)$. Если же $y_k > y_{l-1}$, то рассмотрим еще разность $\Delta_3 = y_k - y_l = y_k - y_{l-1} + \frac{y_{l-1}}{l}$. $\Delta_3 + (k-1)\Delta_1 = (l-1)(y_k - y_{l-1}) + 1 > 1$, откуда max($\Delta_1, \Delta_3$) $\geqslant \frac{1}{k+l-1}$. Итак мы доказали, что разность не меньше $\frac{1}{k+l-1}$. Поэтому для произвольного набора она не меньше $\frac{1}{2(n-1)}$ ($l \leqslant n, k \leqslant n-1$). Такую разность реализовать можно: достаточно, например, рассмотреть набор $x_1 = x_2 = \dots = x_{n-2} = \frac{1}{2}$, $x_{n-1} = 1$, $x_n = 0$. Итак, нашеньшая разность равна $\frac{1}{2(n-1)}$

Л. Г. Лиманов

M209. Для любого треугольника ABC можно вычислить максимум:

$$S = \text{tg}^2 A/2 + \text{tg}^2 B/2 + \text{tg}^2 C/2.$$

Докажите что

a) $S \leqslant 2$ для всех остроугольных и прямоугольных треугольников;

b) $S \geqslant 2$ для многоугольных треугольников с тульным углом, большим или равным 2 arcctg 4/3;

b) среди треугольников с тульным углом $\varphi$ максим, что $\frac{\pi}{2} < \varphi < 2$ arcctg 4/3, имеются $u$ максим, что $S > 2$, $u$ максим, что $S < 2$.

Приведем одно из наиболее коротких решений, близкое к присланному С. Берко-laйко (Белгородская обл.) и А. Грицоряном (Баку).

Из формулы

$$\text{tg} \left( \frac{\pi}{2} - \frac{A}{2} - \frac{B}{2} \right) = \frac{1 - \text{tg} \frac{A}{2} \cdot \text{tg} \frac{B}{2}}{\text{tg} \frac{A}{2} + \text{tg} \frac{B}{2}}$$

следует, что положительные числа $x, y$ и $z$ могут служить тангенсами полиномов $\Delta ABC$ в том и только том случае, когда $xy + yz + zx = 1$. (1)

Такжество (1) позволяет вместе с суммой $S = x^2 + y^2 + z^2$ рассматривать более простую сумму $T = x + y + z$: поскольку $T^2 = S + 2$, то условия $S > 2$, $S = 2$ и $S < 2$ равносильны соответственно условиям $T > 2$, $T = 2$ и $T < 2$.

Задча сводится, таким образом, к следующей.

Пусть $xy + yz + zx = 1$, $x + y + z = T$, $0 < x \leqslant z$, $0 < y \leqslant z$.

Тогда

a) $T \leqslant 2$ при $z \leqslant 1$;

b) $T \geqslant 2$ при $z \geqslant 4/3$;

b) для всякого $z$ между 1 и 4/3 найдется и такие $x, y$, что $T < 2$, и такие $x, y$, что $T > 2$.

Докажем утверждение a), б) и в).

a) Если $z \leqslant 1$, то $S = x^2 + y^2 + z^2 \leqslant xz + yz + z^2 < xy + yz + z^2 = 1 + z^2 \leqslant 2$, так что и $S < 2$, и $T < 2$.

6. Если $z = \frac{4}{3} + d$, $d \geqslant 0$, то $x + y \geqslant \frac{2}{3}$ – d.

Докажем это от противного: предположим что $x + y < \frac{2}{3} - d$.

Тогда

$$xy \leqslant \frac{(x+y)^2}{4} < \frac{1}{9} - \frac{d}{3} + \frac{d^2}{4},$$

$(x+y)z < \left(\frac{2}{3} - d\right)\left(\frac{4}{3} + d\right) = \frac{8}{9} - \frac{2d}{3} - d^2,$

так что

$$1 = xy + (x+y)z < 1 - d - \frac{3d^2}{4} \leqslant 1.$$

Полученное противоречие доказывает, что $x + y \geqslant \frac{2}{3} - d$, и $T = (x+y) + z \geqslant \frac{2}{3} - d + \frac{4}{3} + d = 2.$

b) Пусть теперь $1 < z < \frac{4}{3}$.

Сначала найдем такие $x$ и $y$, что $T < 2$. Возьмем $x = y$. Согласно тождеству (1) тогда $x = y = \sqrt{z^2 + 1} - z$, $T = 2\sqrt{z^2 + 1} - z$. Так как $z < 4/3$, $4(z^2 + 1) < 4 + 4z + z^2$, $2\sqrt{z^2 + 1} < z + 2$, и значит, $T < 2$.

Заметание. Вернушись к исходной формулировке задачи, мы видим, что для равноведренных типуугольных треугольников с типым углом $\varphi < 2$ arcctg $4/3$ сумма $S < 2$.

Теперь найдем такие $x$ и $y$, что $T > 2$. Используя тождество (1), записем $T$ в виде $T = (x+y) + z = \frac{1 - xy}{z} + z$.

Сумма $z + \frac{1}{z} > 2$, $T$ отличается от нее на величины $\frac{xy}{z}$. Так как $y \leqslant z$, то $\frac{xy}{z} \leqslant x$.

Значит, если взять $x < z + \frac{1}{z} - 2$, то $T$ оказывается

40

Жется больше 2. Остается только проверить, что действительное существует $x$ и $y$, удовлетворяющие условиям $0 < x \leq z$, $0 < y \leq z$,

$$xy + yz + zx = 1 \text{ и } x < z + \frac{1}{z} - 2. \quad (2)$$

Воспользовемся тем, что $z > 1$ (отметим, что при $z \leq 1$ таких $x$ и $y$ не существуют, — это следует, например, из пункта a). Согласно (1) $y = \frac{1 - xz}{x + z}$. При $z > 1$ и при $0 < x < \frac{1}{z}$, очевидно, $0 < y < 1$. Итак, для любого $x > 0$ такого, что $x < \frac{1}{z}$ и $x < z + \frac{1}{z} - 2$, при $y = \frac{1 - xz}{x + z}$ условия (2) выполняются. Таким образом, при $1 < z < \frac{4}{3}$, если $0 < x < z + \frac{1}{z} - 2$ и $y = \frac{1 - xz}{x + z}$, то $T > 2$. Задча решения.

Геометрический смысл. Построим три окружности $\alpha$, $\beta$, и $\gamma$ с центрами $A$, $B$ и $C$, которые попарно касаются друг друга внешним образом.

При $S < 2$ существует одна окружность $\delta$, которая касается $\alpha$, $\beta$ и $\gamma$ внешним образом, и одна окружность $\varepsilon$, которая $\alpha$, $\beta$ и $\gamma$ касаются изнутри.

При $S > 2$ две окружности $\delta_1$ и $\delta_2$ касаются $\alpha$, $\beta$ и $\gamma$ внешним образом, кроме того $\alpha$, $\beta$ и $\gamma$ касаются изнутри.

Случай $S = 2$—переходный: одна окружность $\delta$ касается $\alpha$, $\beta$, $\gamma$ внешним образом, кроме того $\alpha$, $\beta$ и $\gamma$ касаются изнутри.

Доказательство этих утверждений можно найти в статье «Сюрпризы» («Квант», 1974, № 1).

М. Л. Гервер

M210. Расстоянием последовательности, состоящее из 3000 цифр $1$ и $2$. В такой последовательности разрешается поменять местами любые две соседние строки цифр. Две последовательности называются эквивалентными, если одну из них можно перевести в другую нескольким максимальным перестановкам. Сколько всего существует нескольенным последовательности?

Решим задачу для последовательностей из 3n цифр. Чтобы не возникло путаницы, греческий буквами будем обозначать последовательности, а латинским — элементы последовательности. Пусть последовательность $\alpha$ состоит из 3n цифр

$$\{a_1, a_2, \dots, a_{3n}\}.$$

Разобъем $\alpha$ на три подоследовательности:

$$\alpha_1 = \{a_1, a_4, a_7, \dots, a_{3k+1}, \dots, a_{3(n-1)+1}\},$$

$$\alpha_2 = \{a_2, a_5, a_8, \dots, a_{3k+2}, \dots, a_{3(n-1)+2}\},$$

$$\alpha_3 = \{a_3, a_6, a_9, \dots, a_{3k}, \dots, a_{3n}\}.$$

Такое развитие будем называть стандартным. Каждый из последовательностей $\alpha_1, \alpha_2, \alpha_3$ стандартного развития из $n$ цифр. Пусть $\beta$ — произвольная последовательность. Через $|\beta|$ обозначаим число единиц в последовательности $\beta$.

Подсчет числа несквивалентных последовательностей основывается на следующей теореме:

Теорема. Пусть $\alpha$ и $\beta$ — две последовательности длины $3n$, $(\alpha_1, \alpha_2, \alpha_3)$ и $(\beta_1, \beta_2, \beta_3)$ — их стандартные разбиения.

Для того чтобы последовательности $\alpha$ и $\beta$ были эквивалентными, необходимо и достаточно, чтобы последовательности $\alpha_1$ и $\beta_1, \alpha_2$ и $\beta_2, \alpha_3$ и $\beta_3$ содержали одинаковое число единиц соответствующего тройкой чисел $(|\alpha_1|, |\alpha_2|, |\alpha_3|)$. Эти числа могут принимать любые значения от 0 до $n$. Следовательно, число несквивалентных последовательностей длины $3n$ равно числу различных упорядоченных троек целых чисел от 0 до $n$. Нетрудно видеть, что число таких троек равно $(n + 1)^3$.

Доказательство теоремы. Пусть мы переставили в последовательности $\alpha = \{a_1, a_2, \dots, a_{3n}\}$ две последовательности цифр: $a_k, a_{k+1}, a_{k+2}$ и $a_{k+3}, a_{k+4}, a_{k+5}$. Эту перестановку можно представить следующим образом: сначала помещали цифры $a_k$ и $a_{k+3}$, затем помещали цифры $a_{k+1}$ и $a_{k+4}$, и наконец, помещали цифры $a_{k+2}$ и $a_{k+5}$. Числа $a_k$ и $a_{k+3}$ — соседние цифры одного и той же подоследовательности стандартного развития $\alpha$; числа $a_{k+1}$ и $a_{k+4}$ — другой, а числа $a_{k+2}$ и $a_{k+5}$ — третьей. Таким образом, в каждом из подоследовательностей $\alpha_1, \alpha_2, \alpha_3$ стандартного развития $\alpha$ мы переставили два соседних члена. Значит, если последовательность $\beta$ получена из последовательности $\alpha$ конечным числом перестановок, то есть, если последовательность $\alpha$ и $\beta$ эквивалентны, то подоследовательность $\beta_1, \beta_2, \beta_3$ стандартного развития $\beta$ существенно перестановки