Процессы и алгоритмы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В каждой строке таблицы 
в некотором порядке стоят числа от 1 до 100, числа в строке не повторяются (в таблице 
строк и 100
столбцов). Разрешается поменять местами в строке два числа, отличающиеся на 1, если они не стоят рядом. Оказалось, что с помощью
таких операций нельзя получить двух одинаковых строк. При каком наибольшем 
это возможно?
Источники:
Подсказка 1:
По условию нельзя одну строку перевести в другую. Что это означает в общем виде?
Подсказка 2:
Каждой строке присущ индивидуальный признак, над которым описанная операция невластна либо власть очень ограничена, то есть с помощью этой операции можно совсем немного изменить этот признак. Разумеется, нам будет проще, если признак будет абсолютно неприступным, ведь тогда гораздо проще делать оценку в силу "фиксированности". Попробуем сначала доказать именно это. Что это за особенность такая?
Подсказка 3:
Может быть, это какой-то арифметический признак? Какая-нибудь сумма квадратов разностей между соседними числами... Или что-нибудь другое?
Подсказка 4:
Спустя время можно осознать, что арифметика не особо-то и вяжется сюда. Значит, думаем дальше. Мы меняем два элемента с разницей в 1. Хмм, попробуем просто поисследовать, что происходит при операции. Например, можно начать с анализа соседних чисел с теми, которые мы меняем...
Подсказка 5:
Пусть последовательность выглядела так: ...abc...def.... Меняем b и e. Знаем, что |b − e| = 1. Интересно, может ли случиться так, что b > c, а e < c?
Подсказка 6:
Конечно, нет. Иначе b ≥ c + 1, e ≤ c − 1, то есть b − e ≥ 2, ошибочка однако... Хм, на какую более общую идею это наталкивает?
Подсказка 7:
Отношения (в плане больше или меньше) сохраняются при перестановке b и e. Кажется, мы на верном пути! Итак, какая же у нас идея?
Подсказка 8:
Если рассмотреть в какой-то строке отношения между всеми соседними, то оно всегда будет оставаться таким же! Хммм, как бы изящно записать эти отношения?
Подсказка 9:
Наверное, с помощью знаков < и >. То есть каждой строке сопоставляем такую последовательность из 99 знаков, назовём её признаком. Получается, если у двух строк разные признаки, то одну из другой не получить. А если совпадают, всегда ли можно?
Подсказка 10:
Оставим это подзадачу для самостоятельного решения, но скажем одно: ответ положительный. Итак, теперь мы знаем, что строк в таблице не больше, чем количество различных признаков. Какую оценку мы тогда получили на n?
Подсказка 11:
n ≤ 2⁹⁹ (осознайте почему). Попробуем же теперь построить пример.
Подсказка 12:
В явном виде строить его довольно трудно. Нужно действовать хитрее! Зафиксируем признак и докажем, что для него можно подобрать нужный набор чисел (доказать это необходимо в общем виде). Это будет ещё одна подзадача для самостоятельного решения) Дело за Вами! Мы в Вас верим!
Сопоставим строке 
…, 
чисел от 1 до 100 последовательность из 99 знаков < и > в соответствии с тем, как упорядочены
соседние числа. То есть если 
то 
-й знак в этой последовательности равен <, в противном случае он равен
>.
Заметим, что разрешённые операции над строкой не меняют соответствующую ей последовательность знаков. Действительно, из пары
чисел 
и 
меняется не более одного и не более чем на 1. Поэтому знак неравенства между ними не может измениться на
противоположный.
Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть
выделенными). При 
…, 
если 
(т.е. 
-й знак <) поставим на место 
наибольшее из не выбранных ранее чисел,
если же 
— наименьшее из не выбранных ранее чисел.
Заметим, что при такой последовательности операций числа, не выбранные за первые 
шагов, будут образовывать отрезок
натурального ряда (а выбранными окажутся несколько наибольших и несколько наименьших чисел от 1 до 100). В частности, 
или
Число 
заменим на единственное оставшееся число.
Нетрудно видеть, что полученная расстановка чисел соответствует выбранной последовательности знаков. Всего выделенных расстановок
будет столько же, сколько и различных последовательностей знаков, то есть 
В силу сказанного выше, разрешёнными операциями
никакие две из выделенных строк нельзя сделать одинаковыми. Таким образом, заполнив таблицу 
выделенными строками, мы
получаем пример для 
Теперь докажем, что из любой строки 
длины 100 можно получить выделенную строку 
с той же расстановкой знаков. Из этого
последует, что 
Предположим, что первые 
знаков данной строки
и выделенной строки
совпадают. Если 
то и сами строки совпадают. Пусть 
Без ограничения общности будем считать, что
В силу сказанного выше наборы чисел 
…, 
и 
…, 
совпадают и образуют отрезок натурального ряда с наименьшим
числом 
Поскольку 
можно менять в строке 
на месте 
с числом на единицу меньшим, пока на месте 
не окажется
число 
Таким образом, мы добились совпадения первых 
символов у нашей строки с выделенной строкой 
Значит, такими операциями
можно из любой строки получить выделенную строку, что завершает доказательство оценки.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
