На окружности некоторым способом расставили натуральные числа от 1 до 21 (каждое число поставлено по одному разу). Затем для каждой пары соседних чисел нашли разность большего и меньшего.
а) Могли ли все полученные разности быть не меньше 11?
б) Могли ли все полученные разности быть не меньше 10?
в) Помимо полученных разностей, для каждой пары чисел, стоящих через одно, нашли разность большего и меньшего. Для какого наибольшего целого числа k можно так расставить числа, чтобы все разности были не меньше k?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1, получая набор 1,…,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1.
L=1
Шаг 2. Для среднего числа в наборе 1,…,N наибольшая возможная разность с любым другим ограничена расстоянием до одного из концов. Это сразу исключает слишком большой порог. Приведённая перестановка проверяется по каждой соседней паре и достигает допустимого порога.
N=21
k=11
Шаг 3. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1, получая набор 1,…,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1.
L=1
Шаг 2. Для среднего числа в наборе 1,…,N наибольшая возможная разность с любым другим ограничена расстоянием до одного из концов. Это сразу исключает слишком большой порог. Приведённая перестановка проверяется по каждой соседней паре и достигает допустимого порога.
N=21
k=10
Шаг 3. Показываем найденное распределение или набор.
Шаг 4. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Вычитаем из всех чисел одну и ту же величину L−1, получая набор 1,…,N. Разности между числами при этом не меняются. Найденную расстановку возвращаем к исходному набору прибавлением L−1.
L=1
Шаг 2. Пусть N=3q. Любые q последовательных по величине чисел отличаются меньше чем на q, поэтому при пороге q они обязаны стоять на круге на расстояниях не меньше трёх мест. На круге из 3q мест это ровно одна из трёх равномерных троек классов мест. Два последовательных по величине блока из q чисел имеют q−1 общих элементов, значит, занимают один и тот же класс. Последовательно сдвигая блок, пришлось бы поместить все N чисел в q мест - противоречие. Порог больше q тем более невозможен. Значит, k≤q−1.
N=21
Шаг 3. Записываем 1,q+1,2q+1,2,q+2,2q+2,…,q,2q,3q по кругу. Соседи отличаются не меньше чем на q, а стоящие через одного - не меньше чем на q−1, в том числе на стыке конца и начала. Поэтому верхняя граница q−1 достигается.