Задача в честь 2026го будующего года

Question

Задача в честь 2026го будующего года

cretty pat Мастер (1558), открыт 3 дня назад

Дана случайная перестановка натуральных чисел от 1 до 2026. Правда ли что в ней всегда можно вычеркнуть сколько то чисел, чтобы образовался блок из 46 подряд идущих чисел, являющихся монотонно возрастающей / убывающей последовательностью?

Answer 1

Да, это утверждение верно. В любой случайной перестановке натуральных чисел от 1 до 2026 всегда можно вычеркнуть некоторые числа так, чтобы образовалась монотонная последовательность из 46 подряд идущих чисел.

Answer 2

Inspiration Высший разум (141704) 3 дня назад

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
При r = s = 46 получается требуемый результат.

cretty patМастер (1558) 2 дня назад

Как так нашли эту теорему? Явно же до этого не знали ее

Inspiration Высший разум (141704) cretty pat, а я сначала попал сюда https://math.stackexchange.com/questions/2149576/every-sequence-of-n21-distinct-real-numbers-contains-a-subsequence-of-length?rq=1

Answer 3

Главное тут – слово «подряд идущих». А раз они идут без пропусков в новой последовательности, значит в исходной перестановке они тоже должны были занимать 46 подряд идущих позиций (потому что если между i-м и (i+1)-м элементом новой последовательности в исходном списке было что-то удалено, то в новой последовательности они всё равно считаются соседними).

Получается, что «вычеркивание» никак не может помочь «выпрямить» кусок длины 46, если в исходной перестановке он не был монотонным. Ведь чтобы сделать именно эти 46 позиций подряд, мы не можем внутри них ничего удалять (иначе это уже не подряд), а удаление снаружи не влияет на то, возрастающий (убывающий) ли там локальный кусок.

Вопрос сводится к тому: «Существует ли в любой перестановке длины 2026 монотонный фрагмент (блок) из 46 подряд идущих элементов?» Если бы ответ был «да», то тогда и вычеркивание не требовалось бы (или требовалось бы только снаружи), а если ответ «нет», то никакими удалениями этот фрагмент всё равно не сделаешь монотонным.

Оказывается, что ответ «нет, не всегда» – то есть можно построить перестановку, в которой никакой кусок длины 46 не будет строго возрастать или убывать. Классический пример – так называемая «зигзагообразная» (или «волнообразная») перестановка:

2, 1, 4, 3, 6, 5, 8, 7, 10, 9, …

и так далее, чередуя подъём и спуск. В такой последовательности каждый локальный кусок из трёх подряд идущих чисел выглядит вроде (2, 1, 4) или (1, 4, 3) и не может быть строго монотонным. Максимальная длина монотонного блока (без пропусков) там получится 2. А раз уже на трёх не получается, то тем более не выйдет сделать кусок из 46 подряд идущих чисел монотонным. Удаление элементов тоже не поможет «склеить» внутри одного и того же куска длины 46 монотонность, ведь чтобы блок был подряд идущим в новой последовательности, мы не можем выбрасывать «внутренние» элементы этого куска.