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

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

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

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

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

  1. Общий сдвиг чисел
  2. Среднее число при чётном NN

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

  3. Ответ: нет

    Сначала: Среднее число при чётном NN

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

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

  5. Среднее число при чётном NN

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

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

    Сначала: Среднее число при чётном NN

  7. Ответ: да

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

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

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

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

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

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

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

  11. Ответ

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

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

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

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

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

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

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

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

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

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

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

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