Комбинаторика на Всесибе: игры, графы, конструктивы

Первое решение

Если записать числа от 1 до по часовой стрелке, то хорошими будут все пары, содержащие число кроме пар соседних с чисел и Всего пары.

Докажем индукцией по что если по кругу выписаны все натуральные числа от 1 до то количество хороших пар всегда равно вне зависимости от порядка записи.

База индукции:

Числа от 1 до 4 можно выписать по кругу четырьмя различными способами:

Хорошими в них будут единственные пары:

При этом База индукции выполнена.

Шаг индукции.

Пусть утверждение индукции выполнено для всех количеств чисел от 4 до докажем для Рассмотрим все натуральные числа от 1 до выписанные в произвольном порядке. Заметим, что ни одна хорошая пара чисел не содержит число 1, и пара чисел, записанных слева и справа от 1, образуют хорошую пару. Назовем такую пару маленькой.

Теперь вычеркнем единицу, получим выписанных чисел от 2 до Пары, которые были хорошим для исходных чисел, кроме маленькой, останутся хорошими и для полученных чисел, верно и обратное.

Количество хороших пар для полученных чисел, по предположению индукции, равно Все эти пары останутся хорошими, если вернуть назад вычеркнутую единицу, и ещё к ним добавится новая пара чисел — маленькая. Всего получаем хороших пар, что доказывает шаг индукции.

В итоге ответ — 97 хороших пар чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение

Рассмотрим произвольную запись по кругу в некотором порядке всех натуральных чисел от 1 до 100. Будем считать их расположенными в вершинах правильного 100-угольника, обозначим его Сначала докажем, что хорды, соответствующие двум разным хорошим парам чисел, не могут пересекаться по внутренним точкам.

Рассмотрим две хороших пары чисел в которых все 4 числа различны. Можно считать, что Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то числа и лежат по разные стороны от хорды и оба больше что противоречит «хорошести» пары

Теперь предположим, что проведены хорды для всех хороших пар выписанных чисел. Как мы только что доказали, они не пересекаются по внутренним точкам, поэтому разбивают наш 100-угольник на несколько многоугольников с вершинами в вершинах 100-угольника. Если среди них есть многоугольник с более, чем тремя вершинами, рассмотрим самое маленькое из чисел в вершинах обозначим его за соседние с ним в числа обозначим за и Рассмотрим возникающие при этом варианты расположения соответствующих им вершин в 100-угольнике

1) Все три числа записаны в трёх последовательных вершинах Тогда будет хорошей хордой что противоречит предположению о том, что все хорошие хорды уже проведены.

2) Одна из пар является хорошей в а вторая образует пару соседних вершин Можно считать, что хорошей является пара Так как все числа, лежащие в относительно с другой стороны от хорды меньше Тогда хорда снова будет не проведённой хорошей хордой

3) и являются хорошими в В этом случае, так как маленькие числа для хорды лежат в с другой относительно стороны, а маленькие числа для хорды лежат в с другой относительно стороны. Следовательно, хорда будет непроведенной хорошей хордой 100-угольника, у которой маленькие числа расположены в с той же стороны, что и При том числа записаны в трёх последовательных вершинах многоугольника с более, чем тремя вершинами, поэтому не может быть стороной и тем более стороной

Таким образом, если хотя бы один из многоугольников, на которые разбивают 100-угольник хорошие хорды, не является треугольником, то всегда можно провести ещё одну хорошую хорду. Следовательно, все хорошие хорды разбивают 100-угольник на треугольники для любого порядка записи чисел от 1 до 100 в его вершинах.

Сумма величин всех углов 100-угольника равна (сумма внутренних углов выпуклого -угольника равна В данной ситуации, когда все вершины треугольников лежат в вершинах она равна сумме углов во всех треугольниках разбиения. Сумма углов в каждом треугольнике разбиения равна поэтому общее число треугольников разбиения равно 98. В общем числе сторон всех треугольников разбиения каждая хорда учитывается дважды, а каждая сторона — один раз. Следовательно, количество проведённых хороших хорд равно для любого порядка записи чисел от 1 до 100 в его вершинах.