Можно ли написать по кругу 8 чисел...?

[Ktina]

Можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 25, если требуется, чтобы любые два соседних числа отличались на 5 или 7? Приведите пример или докажите, что это невозможно.

У меня получилось так: 25, 20, 13, 8, 1, 6, 11, 18, круг замкнулся.

Напрашивается вопрос, обязательно ли использовать число 25?
Иными словами, можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 24, если требуется, чтобы любые два соседних числа отличались на 5 или 7?

Оказывается, и это можно: 20, 13, 6, 1, 8, 3, 10, 15, круг замкнулся.

А вот можно ли, чтобы все числа не превосходили 19?
У меня, почему-то, не получается.

Пожалуйста, помогите решить.
Заранее благодарю.

[Cash]

Компьютер утверждает, что нельзя.

[Ktina]

Cash
Спасибо, конечно, но можно ли решить вручную?

[Cash]

А смысл?

[Dmitriy40]

Смысл разве лишь в том чтобы выявить взаимосвязь количества чисел и множества допустимых разностей. Т.е. решить задачу в максимально общем виде.

[mihiv]

А такой вариант: 19,14, 7, 12, 5, 10, 17, 12.

[grizzly]

mihiv в сообщении #1184062 писал(а):

12, [...] ,12

[mihiv]

А, точно, должны быть все различные.

[SVD-d]

Очевидно, нельзя.
Только, чтобы разобраться, почему, придётся перебрать варианты. Благо, не так уж их и много.

Сначала для простоты примем одно из чисел - а именно, минимальное - равным единице. Логично, что если среди чисел в кольце все будут больше, то всегда можно вычесть из всех восьми чисел столько, чтобы минимальное было равно единице, и тогда мы сможем уменьшить максимальное значение.
Очевидно, так как наше выбранное число минимально, то соседние будут больше на пять и семь соответственно. То есть, где-то в центре нашего кольца есть основа:
$..., 6, 1, 8, ...$
Из шестёрки мы не можем вычесть ни пять (потому что все числа должны быть разными), ни семь (потому что минимальное по условию у нас уже есть). Значит, слева от неё может быть только два числа: либо 11, либо 13. Справа от восьмёрки может быть уже три числа: 3, 13 или 15. Справа от тройки может стоять только 10. Потому что вычитать из неё уже нечего, а слева уже стоит 8. Думаю, надо всё это записать, пока не забыл. Какое бы ни было кольцо, у него в центре может быть всего лишь пять вариантов центра:
а) $..., 11, 6, 1, 8, 3, 10, ...$
б) $..., 11, 6, 1, 8, 13, ...$
в) $..., 11, 6, 1, 8, 15, ...$
г) $..., 13, 6, 1, 8, 3, 10, ...$
д) $..., 13, 6, 1, 8, 15, ...$

Казалось бы, вариантов уже довольно много, а если мы пойдём дальше, так станет ещё больше. Но на самом деле, нет. Теперь всё только упростится.

Слева от 11 может стоять только 4 или 18.
Слева от 13 - только 18 или 20. Справа от 13, кстати, тоже.
Справа от 15 - больше всего вариантов: 10, 20 и 22.

$|10-4| = 6; |10-18| = 8; |10-20| = 10$. То есть, для основы (а) невозможно добавить в кольцо такое число, чтобы оно сошлось. А для основы (г) такое число есть: $20, 13, 6, 1, 8, 3, 10, 15$.

Я вначале хотел переписать всё словами, но давайте для наглядности запишу оставшиеся варианты:

б1) $..., 4, 11, 6, 1, 8, 13, ...$
б2) $..., 18, 11, 6, 1, 8, 13, ...$
в1) $..., 4, 11, 6, 1, 8, 15, ...$
в2) $..., 18, 11, 6, 1, 8, 15, ...$
д1) $..., 18, 13, 6, 1, 8, 15, ...$
д2) $..., 20, 13, 6, 1, 8, 15, ...$

Числа справа не пишу, чтобы не занимать место и не тратить время, тем более что они указаны сверху.
Слева от четвёрки можно поставить только девятку, но между девяткой и 13, равно как между 9 и 15, нельзя поставить никакое число. (б1) и (в1) сразу выбрасываются.

$|18-20| = 2; |22-20| = 2; |10-20| = 10$. Между этими тремя парами можно поставить такие числа, которые бы объединили кольцо: 25 или 13, 27 или 15, а также 15 соответственно. Выбрасывая 13 и 15 из тех групп, где они уже есть, получаем весьма ограниченное количество вариантов.

Подводим итог. При условии, что числа могут различаться только на 5 или на 7, есть только пять вариантов минимальных колец:
(г) $20, 13, 6, 1, 8, 3, 10, 15$
(б2) $25, 18, 11, 6, 1, 8, 13, 20$
(в2) $25, 18, 11, 6, 1, 8, 15, 20$
(д1) $25, 18, 13, 6, 1, 8, 15, 20$
(д2) $27, 20, 13, 6, 1, 8, 15, 22$

Прибавляя одинаковые числа ко всем элементам кольца, можно получить сколь угодно большие наборы.

Остаётся два вопроса.
1) Насколько лень кому бы то ни было будет расписывать эти наборы для общего случая кольца из $N$ элементов, различающихся на $x_{1}$ и $x_{2}$, и
2) откуда вы берёте такие вопросы.

[Cash]

SVD-d в сообщении #1184082 писал(а):

Подводим итог. При условии, что числа могут различаться только на 5 или на 7, есть только пять вариантов минимальных колец:

Что скажете, например, про это:
$1, 6, 11, 18, 13, 20, 15, 8, 1$

(Оффтоп)

Запрет на вычислительную технику в чисто переборной задаче, имхо, бред. Пусть и количество вариантов сравнительно невелико.

[grizzly]

SVD-d в сообщении #1184082 писал(а):

есть только пять вариантов минимальных колец

Вариантов есть ровно столько же, сколько есть способов записать строку длины 8 из чисел $\{5;-5;7;-7\}$ так, чтобы в ней сумма подряд идущих чисел обнулялась только для всей строки (и ни для какой подстроки), а положительных пятёрок (соответственно, семёрок) было бы столько же, сколько и отрицательных. Строки, которые можно получить друг из друга циклическими перестановками, считаются эквивалентными. (Зеркальные тоже эквивалентны, наверное?)

Например, для строки $\{-5;-5;-5;7;5;5;5;-7\}$ получим не упоминавшееся ранее кольцо:
$23,16,11,6,1,8,13,18,23$

Это на уровне идеи, но я уверен, что подобная комбинаторная задача вполне по силам ТС, который пока не предъявил никаких попыток решения

[arseniiv]

grizzly в сообщении #1184134 писал(а):

а положительных пятёрок (соответственно, семёрок) было бы столько же, сколько и отрицательных

А зачем это ограничение, если уже есть ограничение на обнуление всей суммы? Для других параметров оно может и не следовать из этого. Скажем, $(-5,1,1,1,1,1)$ для 6 чисел и модулей разностей $\{1,5\}$.

[grizzly]

arseniiv в сообщении #1184146 писал(а):

А зачем это ограничение, если уже есть ограничение на обнуление всей суммы?Для других параметров оно может и не следовать из этого.

Да, конечно. Я это видел сперва, а потом отвлёкся на частности.