Верхняя граница для двух шагов

Пусть N=3qN=3q. Любые qq последовательных по величине чисел отличаются меньше чем на qq, поэтому при пороге qq они обязаны стоять на круге на расстояниях не меньше трёх мест. На круге из 3q3q мест это ровно одна из трёх равномерных троек классов мест. Два последовательных по величине блока из qq чисел имеют q−1q-1 общих элементов, значит, занимают один и тот же класс. Последовательно сдвигая блок, пришлось бы поместить все NN чисел в qq мест: противоречие. Порог больше qq тем более невозможен. Значит, k≤q−1k\leq q-1.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 2. Пусть N=3qN=3q. Любые qq последовательных по величине чисел отличаются меньше чем на qq, поэтому при пороге qq они обязаны стоять на круге на расстояниях не меньше трёх мест. На круге из 3q3q мест это ровно одна из трёх равномерных троек классов мест. Два последовательных по величине блока из qq чисел имеют q−1q-1 общих элементов, значит, занимают один и тот же класс. Последовательно сдвигая блок, пришлось бы поместить все NN чисел в qq мест — противоречие. Порог больше qq тем более невозможен. Значит, k≤q−1k\leq q-1.
N=21N=21

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу