Разности соседей и стоящих через одного

Последовательность применённых правил и переходов в пунктах задачи.

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

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Общий сдвиг чисел
  2. Разности только соседей

    Сначала: Общий сдвиг чисел

  3. Ответ: нет

    Сначала: Разности только соседей

  4. Общий сдвиг чисел

    Сначала: Ответ: нет

  5. Разности только соседей

    Сначала: Общий сдвиг чисел

  6. Конструкция

    Сначала: Разности только соседей

  7. Ответ: да

    Сначала: Конструкция

  8. Общий сдвиг чисел

    Сначала: Ответ: да

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

    Сначала: Общий сдвиг чисел

  10. Достижение порога q−1q-1

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

  11. Ответ

    Сначала: Достижение порога q−1q-1

Разобранный пример

На окружности некоторым способом расставили натуральные числа от 1 до 21 (каждое число поставлено по одному разу). Затем для каждой пары соседних чисел нашли разность большего и меньшего.

а) Могли ли все полученные разности быть не меньше 11?

б) Могли ли все полученные разности быть не меньше 10?

в) Помимо полученных разностей, для каждой пары чисел, стоящих через одно, нашли разность большего и меньшего. Для какого наибольшего целого числа kk можно так расставить числа, чтобы все разности были не меньше kk?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1L-1, получая набор 1, …, N1,\,\ldots,\,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1L-1.
L=1L=1
Шаг 2. Для среднего числа в наборе 1, …, N1,\,\ldots,\,N наибольшая возможная разность с любым другим ограничена расстоянием до одного из концов. Это сразу исключает слишком большой порог. Приведённая перестановка проверяется по каждой соседней паре и достигает допустимого порога.
N=21N=21
k=11k=11
Шаг 3. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1L-1, получая набор 1, …, N1,\,\ldots,\,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1L-1.
L=1L=1
Шаг 2. Для среднего числа в наборе 1, …, N1,\,\ldots,\,N наибольшая возможная разность с любым другим ограничена расстоянием до одного из концов. Это сразу исключает слишком большой порог. Приведённая перестановка проверяется по каждой соседней паре и достигает допустимого порога.
N=21N=21
k=10k=10
Шаг 3. Показываем найденное распределение или набор.
T=(11;1;12;2;13;3;14;4;15;5;16;6;17;7;18;8;19;9;20;10;21)\mathcal T=\left(11;1;12;2;13;3;14;4;15;5;16;6;17;7;18;8;19;9;20;10;21\right)
Шаг 4. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1L-1, получая набор 1, …, N1,\,\ldots,\,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1L-1.
L=1L=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
Шаг 3. Записываем 1, q+1, 2q+1, 2, q+2, 2q+2, …, q, 2q, 3q1,\,q+1,\,2q+1,\,2,\,q+2,\,2q+2,\,\ldots,\,q,\,2q,\,3q по кругу. Соседи отличаются не меньше чем на qq, а стоящие через одного - не меньше чем на q−1q-1, в том числе на стыке конца и начала. Поэтому верхняя граница q−1q-1 достигается.
T=(1;8;15;2;9;16;3;10;17;4;11;18;5;12;19;6;13;20;7;14;21)\mathcal T=\left(1;8;15;2;9;16;3;10;17;4;11;18;5;12;19;6;13;20;7;14;21\right)
Шаг 4. Записываем найденное значение.
66

Открыть задачу целиком

Попробовать самостоятельно