Всесиб 2025, 10 класс, задача 5

Ответ. .

Решение 1. Доказать ответ проще, чем додуматься до него, и осознать, что он единственный. Например, если записать числа от до по часовой стрелке, то хорошими будут все пары, содержащие число , кроме пар и соседних с чисел, всего пары.
Докажем индукцией по , что, если по кругу выписаны все натуральные числа от до , то, независимо от порядка записи, количество хороших пар всегда равно .
База индукции . Числа от до можно выписать по кругу четырьмя различными способами: , , , . Хорошими в них будут единственные пары, соответственно: , , , . При этом - база индукции выполнена.
Шаг индукции. Пусть утверждение индукции выполнено для всех количеств чисел, от до , докажем утверждение для . Рассмотрим выписанные в произвольном порядке все натуральные числа от до . Заметим, что ни одна хорошая пара чисел не содержит число , и пара чисел, записанных слева и справа от , образуют хорошую пару, назовём её маленькой. Теперь вычеркнем единицу, получим выписанных чисел от до . Пары, которые были хорошим для исходных чисел, кроме маленькой, останутся хорошими и для полученных чисел, верно и обратное. Количество хороших пар среди для полученных чисел, по предположению индукции, равно . Все эти пары останутся хорошими, если вернуть назад вычеркнутую единицу, и ещё к ним добавится новая пара чисел, соседних слева и справа от , то есть маленькая. Всего получаем хороших пар, что и доказывает шаг индукции.
Решение 2. Рассмотрим произвольную запись по кругу в некотором порядке всех
натуральных чисел от до . Будем считать их расположенными в вершинах правильного
-угольника, обозначим его С. Сначала докажем, что хорды, соответствующие двум
разным хорошим парам чисел, не могут пересекаться по внутренним точкам. Рассмотрим
две хороших пары чисел , , в которых все числа различны, можно считать, что
. Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то
числа c и d лежат по разные стороны от хорды и оба больше a, что противоречит
«хорошести» пары a, b.
Теперь предположим, что проведены хорды для всех хороших пар выписанных чисел.
Как мы только что доказали, они не пересекаются по внутренним точкам, поэтому
разбивают наш -угольник на несколько многоугольников с вершинами в вершинах -угольника. Если среди них есть многоугольник М с более, чем тремя вершинами,
рассмотрим самое маленькое из чисел в вершинах М, обозначим его за x, соседние с ним в
М числа обозначим за y и z. Рассмотрим возникающие при этом варианты расположения
соответствующих им вершин в -угольнике С.
) Все три числа y, x, z записаны в трёх последовательных вершинах С. Тогда хорда yz будет новой хорошей хордой С, что противоречит предположению о том, что все хорошие
хорды уже проведены.
) Одна из пар x, y и x, z является хорошей в С, а вторая образует пару соседних вершин
С. Можно считать, что хорошей является пара x, y . Ввиду неравенства , все числа,
лежащие в С от хорды с другой, по сравнению с z, стороны, меньше x . Тогда хорда
снова будет не проведённой хорошей хордой С.
) Обе пары x, y и x, z являются хорошими в С. В этом случае, ввиду неравенств , , маленькие числа для хорды лежат в С с другой, по сравнению с z, стороны,
а маленькие числа для хорды лежат в С с другой, по сравнению с y, стороны.
Следовательно, хорда будет непроведённой хорошей хордой -угольника, у
которой маленькие числа расположены в С с той же стороны, что и x. При этом числа y, x,
z записаны в трёх последовательных вершинах многоугольника М с более, чем тремя
вершинами, поэтому не может быть стороной М, и тем более стороной С.
Таким образом, если хотя бы один из многоугольников, на которые разбивают -угольник хорошие хорды, не является треугольником, то всегда можно провести ещё одну
хорошую хорду. Следовательно, все хорошие хорды разбивают -угольник на
треугольники для любого порядка записи чисел от до в его вершинах. Сумма величин
всех углов -угольника С равна ∙ , в данной ситуации, когда все вершины
треугольников лежат в вершинах С, она равна сумме углов во всех треугольниках
разбиения. Сумма углов в каждом треугольнике разбиения равна , поэтому общее
число треугольников разбиения равно . В общем числе ∙ сторон всех треугольников
разбиения каждая хорда учитывается дважды, а каждая сторона – один раз. Следовательно,
количество проведённых хороших хорд равно ( ∙ ): для любого порядка
записи чисел от до в его вершинах.