Разделы 
Дополнительно
Задача по математике - 3304
2019-06-02 
Для чисел $1, \cdots, 1999$, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд. Найдите расстановку чисел, при которой полученная сумма наибольшая.
Решение:
Лемма. Пусть по окружности расставлено 1999 различных положительных чисел $a_1, a_2, \cdots, a_{1999}$, и пусть $a_1 > a_{1998}$. Для всех $2 \leq i \leq 999$ проделаем следующую операцию: числа $a_i$ и $a_{1999-i}$ поменяем местами, если $a_i < a_{1999-i}$, и не будем менять в противном случае. Если при этом хотя бы одна пара чисел поменялась местами, то сумма произведений десяток чисел, идущих подряд, увеличилась.
Доказательство леммы. Рассмотрим симметричные группы по 10 чисел: $a_i, \cdots, a_{i+9}$ и $a_{1999-i}, \cdots, a_{1990-i}$. Покажем, что сумма произведений в таких группах не уменьшилась, причем хотя бы в одной группе она увеличилась. Из этого будет следовать утверждение леммы.
Пусть $z$ - произведение чисел, содержащихся одновременно и в первой, и во второй группе (если таковых нет, то считаем $z = 1$); $x$ и $x^{ \prime}$ - произведения чисел, содержащихся соответственно только в первой и только во второй группе, оставшихся на своем месте после проведения наших операций; $у$ и $у^{ \prime}$ - произведение чисел, содержащихся соответственно только в первой и только во второй группе, поменявшихся местами после проделанных операций (опять же, если таких чисел нет, то считаем, что соответствующее произведение равно 1). Тогда сумма произведений чисел в рассматриваемых двух группах до операции равна $s_1 = zxy + zx^{ \prime}y^{ \prime}$, а после операции $s_2 = zxу^{ \prime} + zx^{ \prime}у$. Имеем: $s_1 - s_2 = z(x - x^{ \prime})(у - у^{ \prime})$. Нетрудно видеть, что $x \geq x^{ \prime}$, и $у \leq у^{ \prime}$. Значит, $s_1 - s_2 \leq 0$.
Осталось доказать, что если в результате проделанной операции не все числа остались на своих местах, то хотя бы для одной пары симметричных групп из 10 чисел эта разность будет строго отрицательна. Нетрудно видеть, что $y^{ \prime} > y$, если хотя бы одна пара чисел (из данной десятки) поменялась. Если же хотя бы одна пара чисел не поменялась, то $x^{ \prime} < x$, так как все числа различны. Значит, достаточно показать, что найдутся две симметричные группы по 10 чисел для которых хотя бы одна пара не поменялась, и хотя бы одна пара поменялась (напомним, что $a_1$ и $a_1998$ не поменялись местами). Но это очевидно. Лемма доказана.
Решение задачи. Будем считать, что числа $1, 2, \cdots, 1999$ расставлены так, что дуги между соседними числами равны. Пусть числа расставлены оптимальным образом, т. е. так, что сумма произведений десяток соседних чисел максимальна. Проведем какую-нибудь ось симметрии 1999-угольника (это - диаметр, проходящий через одно из чисел $k$ и середину противоположной дуги). Тогда для всех пар чисел, симметричных относительно этого диаметра, меньшие числа расположены в одном полукруге, а большие - в другом. Действительно, занумеруем числа переменными $a_1, \cdots, a_1999$ по кругу, начиная с большего из чисел, соседних с числом $k$, и заканчивая числом $k$. Тогда $a_1 > a_1998$, так что можно применить лемму: так как расстановка оптимальная, никакая пара чисел не поменяется местами, а значит, большие числа расположены в одном полукруге, а меньшие - в другом.
Оказывается, что с точностью до поворотов и симметрий существует единственная расстановка чисел, удовлетворяющая этому свойству для всех диаметров. Действительно, число 2 должно быть рядом с числом 1. Иначе найдется диаметр, отделяющий число 2 от числа 1, причем 1 и 2 не симметричны относительно этого диаметра. Обозначим числа, симметричные числам 1 и 2 относительно этого диаметра, через $A$ и $B$ соответственно. Тогда $A > 1$ и $2 < B$, что противоречит оптимальности в силу леммы.
Далее строим искомую расстановку по индукции. Пусть мы доказали, что числа $1, 2, \cdots, 2k (1 \leq k \leq 998)$ расставлены как в ответе, т. е. в порядке (для определенности по часовой стрелке) $2k, 2k - 2, \cdots, 2, 1, 3, \cdots, 2k - 1$ подряд. Обозначим через $A$ и $B$ соответственно числа, следующее за $2k$ против часовой стрелки и следующее за $2k - 1$ по часовой стрелке (рис.). Предположим, число $2k + 1$ отлично от $A$ и $B$. Тогда пусть $C$ - число, следующее за $2k + 1$ по часовой стрелке. $C$ отлично от $1, 2, \cdots, 2k$. Числа $C$ и $2k - 1$, а также $2 k + 1$ и $B$ симметричны относительно одного и того же диаметра, но $C > 2k - 1$, а $2k + 1 < B$ - противоречие. Значит, либо $A = 2k + 1$, либо $B = 2k + 1$. Но предположение $A = 2k + 1$ сразу приводит к противоречию - достаточно рассмотреть диаметр, относительно которого симметричны числа $2k$ и $2k - 1$. Значит, $B = 2k + 1$.
Аналогично доказывается, что $A = 2k + 2$. Это завершает доказательство индуктивного перехода.
Ответ: Искомая расстановка изображена на рис. (или получается из нее поворотом или симметрией).
Для чисел $1, \cdots, 1999$, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд. Найдите расстановку чисел, при которой полученная сумма наибольшая.
Решение:
Лемма. Пусть по окружности расставлено 1999 различных положительных чисел $a_1, a_2, \cdots, a_{1999}$, и пусть $a_1 > a_{1998}$. Для всех $2 \leq i \leq 999$ проделаем следующую операцию: числа $a_i$ и $a_{1999-i}$ поменяем местами, если $a_i < a_{1999-i}$, и не будем менять в противном случае. Если при этом хотя бы одна пара чисел поменялась местами, то сумма произведений десяток чисел, идущих подряд, увеличилась.
Доказательство леммы. Рассмотрим симметричные группы по 10 чисел: $a_i, \cdots, a_{i+9}$ и $a_{1999-i}, \cdots, a_{1990-i}$. Покажем, что сумма произведений в таких группах не уменьшилась, причем хотя бы в одной группе она увеличилась. Из этого будет следовать утверждение леммы.
Пусть $z$ - произведение чисел, содержащихся одновременно и в первой, и во второй группе (если таковых нет, то считаем $z = 1$); $x$ и $x^{ \prime}$ - произведения чисел, содержащихся соответственно только в первой и только во второй группе, оставшихся на своем месте после проведения наших операций; $у$ и $у^{ \prime}$ - произведение чисел, содержащихся соответственно только в первой и только во второй группе, поменявшихся местами после проделанных операций (опять же, если таких чисел нет, то считаем, что соответствующее произведение равно 1). Тогда сумма произведений чисел в рассматриваемых двух группах до операции равна $s_1 = zxy + zx^{ \prime}y^{ \prime}$, а после операции $s_2 = zxу^{ \prime} + zx^{ \prime}у$. Имеем: $s_1 - s_2 = z(x - x^{ \prime})(у - у^{ \prime})$. Нетрудно видеть, что $x \geq x^{ \prime}$, и $у \leq у^{ \prime}$. Значит, $s_1 - s_2 \leq 0$.
Осталось доказать, что если в результате проделанной операции не все числа остались на своих местах, то хотя бы для одной пары симметричных групп из 10 чисел эта разность будет строго отрицательна. Нетрудно видеть, что $y^{ \prime} > y$, если хотя бы одна пара чисел (из данной десятки) поменялась. Если же хотя бы одна пара чисел не поменялась, то $x^{ \prime} < x$, так как все числа различны. Значит, достаточно показать, что найдутся две симметричные группы по 10 чисел для которых хотя бы одна пара не поменялась, и хотя бы одна пара поменялась (напомним, что $a_1$ и $a_1998$ не поменялись местами). Но это очевидно. Лемма доказана.
Решение задачи. Будем считать, что числа $1, 2, \cdots, 1999$ расставлены так, что дуги между соседними числами равны. Пусть числа расставлены оптимальным образом, т. е. так, что сумма произведений десяток соседних чисел максимальна. Проведем какую-нибудь ось симметрии 1999-угольника (это - диаметр, проходящий через одно из чисел $k$ и середину противоположной дуги). Тогда для всех пар чисел, симметричных относительно этого диаметра, меньшие числа расположены в одном полукруге, а большие - в другом. Действительно, занумеруем числа переменными $a_1, \cdots, a_1999$ по кругу, начиная с большего из чисел, соседних с числом $k$, и заканчивая числом $k$. Тогда $a_1 > a_1998$, так что можно применить лемму: так как расстановка оптимальная, никакая пара чисел не поменяется местами, а значит, большие числа расположены в одном полукруге, а меньшие - в другом.
Оказывается, что с точностью до поворотов и симметрий существует единственная расстановка чисел, удовлетворяющая этому свойству для всех диаметров. Действительно, число 2 должно быть рядом с числом 1. Иначе найдется диаметр, отделяющий число 2 от числа 1, причем 1 и 2 не симметричны относительно этого диаметра. Обозначим числа, симметричные числам 1 и 2 относительно этого диаметра, через $A$ и $B$ соответственно. Тогда $A > 1$ и $2 < B$, что противоречит оптимальности в силу леммы.
Далее строим искомую расстановку по индукции. Пусть мы доказали, что числа $1, 2, \cdots, 2k (1 \leq k \leq 998)$ расставлены как в ответе, т. е. в порядке (для определенности по часовой стрелке) $2k, 2k - 2, \cdots, 2, 1, 3, \cdots, 2k - 1$ подряд. Обозначим через $A$ и $B$ соответственно числа, следующее за $2k$ против часовой стрелки и следующее за $2k - 1$ по часовой стрелке (рис.). Предположим, число $2k + 1$ отлично от $A$ и $B$. Тогда пусть $C$ - число, следующее за $2k + 1$ по часовой стрелке. $C$ отлично от $1, 2, \cdots, 2k$. Числа $C$ и $2k - 1$, а также $2 k + 1$ и $B$ симметричны относительно одного и того же диаметра, но $C > 2k - 1$, а $2k + 1 < B$ - противоречие. Значит, либо $A = 2k + 1$, либо $B = 2k + 1$. Но предположение $A = 2k + 1$ сразу приводит к противоречию - достаточно рассмотреть диаметр, относительно которого симметричны числа $2k$ и $2k - 1$. Значит, $B = 2k + 1$.
Аналогично доказывается, что $A = 2k + 2$. Это завершает доказательство индуктивного перехода.
Ответ: Искомая расстановка изображена на рис. (или получается из нее поворотом или симметрией).
