ВсОШ 2023, 11 класс, задача 3
( баллов) В каждой строке таблицы в некотором порядке стоят числа от до , числа в строке не повторяются (в таблице строк и столбцов). Разрешается поменять местами в строке два числа, отличающиеся на , если они не стоят рядом. Оказалось, что с помощью таких операций нельзя получить двух одинаковых строк. При каком наибольшем это возможно? (М. Антипов)
Ответ
Ответ. .
Решение. Сопоставим строке чисел от до последовательность из знаков и в соответствии с тем, как упорядочены соседние числа. То есть если , то -й знак в этой последовательности равен , в противном случае он равен . Заметим, что разрешённые операции над строкой не меняют соответствующую ей последовательность знаков. Действительно, из пары чисел и меняется не более одного и не более чем на . Поэтому знак неравенства между ними не может измениться на противоположный.
Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть выделенными). При если (т.е. -й знак ) поставим на место наибольшее из не выбранных ранее чисел, если же - наименьшее из не выбранных ранее чисел. Заметим, что при такой последовательности операций числа, не выбранные за первые шагов, будут образовывать отрезок натурального ряда (а выбранными окажутся несколько наибольших и несколько наименьших чисел от до ). В частности, или . Число заменим на единственное оставшееся число.
Нетрудно видеть, что полученная расстановка чисел соответствует выбранной последовательности знаков. Всего выделенных расстановок будет столько же, сколько и различных последовательностей знаков, то есть . В силу сказанного выше, разрешёнными операциями никакие две из выделенных строк разрешёнными операциями нельзя сделать одинаковыми. Таким образом, заполнив таблицу выделенными строками, мы получаем пример для .
Теперь докажем, что из любой строки длины можно получить выделенную строку с той же расстановкой знаков. Из этого последует, что . Предположим, что первые знаков данной строки и выделенной строки совпадают. Если , то и сами строки совпадают. Пусть . Без ограничения общности будем считать, что . В силу сказанного выше наборы чисел и совпадают и образуют отрезок натурального ряда с наименьшим числом . Поскольку , можно менять в строке на месте с числом на единицу меньшим, пока на месте не окажется число . Таким образом, мы добились совпадения первых символов у нашей строки с выделенной строкой . Значит, такими операциями можно из любой строки получить выделенную строку, что завершает доказательство оценки.