Может ли оказаться, что сумма любых двух идущих подряд чисел делится хотя бы на одно из чисел 4 и 7?

По кругу в каком-то порядке расставлены числа от 1 до 9. Может ли оказаться, что сумма любых двух идущих подряд чисел делится хотя бы на одно из чисел 4 и 7?

-----------------------------------------------------

Бросить курить, завязать с выпивкой и начать ходить в спортзал Настя с Дашей ещё кое-как смогли. А вот отказаться от выкатывания пудры оказалось выше их сил.

Цитата
sergeyklykov
$179526843$

1.Стоит отметить, что указанное решение единственно, конечно с точностью до круговой перестановки и направления обхода (по или против часовой).

2. Предлагаю решить эту же задачу с другим набором чисел, например от 1 до 15. Здесь уже прямой перебор во множестве всех перестановок не пройдёт, т.к. 15! больше триллиона. Сколько всего будет решений?

Цитата
kitonum

Цитата
sergeyklykov
$179526843$

1.Стоит отметить, что указанное решение единственно, конечно с точностью до круговой перестановки и направления обхода (по или против часовой).

2. Предлагаю решить эту же задачу с другим набором чисел, например от 1 до 15. Здесь уже прямой перебор во множестве всех перестановок не пройдёт, т.к. 15! больше триллиона. Сколько всего будет решений?

Для чисел от 1 до 15 получается 348240 решений, если считать различными все перестановки. Если циклические сдвиги считать одной и той же расстановкой, то 23216, а если ещё не различать обход по часовой и против часовой стрелки — 11608.

Перебирать все 15! перестановок при этом не нужно. Можно построить граф: соединить числа a и b, если a+b делится на 4 или на 7, а затем посчитать гамильтоновы циклы динамикой по подмножествам.

Для исходной задачи с числами от 1 до 9 такой цикл, кстати, единственен с точностью до поворота и отражения.

-----------------------------------------------------

Бросить курить, завязать с выпивкой и начать ходить в спортзал Настя с Дашей ещё кое-как смогли. А вот отказаться от выкатывания пудры оказалось выше их сил.

Цитата
xenia1996
...
Для чисел от 1 до 15 получается 348240 решений, если считать различными все перестановки. Если циклические сдвиги считать одной и той же расстановкой, то 23216, а если ещё не различать обход по часовой и против часовой стрелки — 11608.

Перебирать все 15! перестановок при этом не нужно. Можно построить граф: соединить числа a и b, если a+b делится на 4 или на 7, а затем посчитать гамильтоновы циклы динамикой по подмножествам...

Спасибо! У меня получились те же ответы.

Это хорошая идея - сведение к поиску гамильтоновых циклов. Здесь даже ничего программировать не нужно. Например, в Maple есть встроенная функция GraphTheory:-TravelingSalesman, которая находит такие циклы.

Я решал построением дерева всех возможных вариантов, начиная с 1. После первого шага получаем варианты, начинающиеся с чисел:
[1, 3], [1, 6], [1, 7], [1, 11], [1, 13], [1, 15]
После второго шага - с чисел:
[1, 3, 4], [1, 3, 5], [1, 3, 9], [1, 3, 11], [1, 3, 13], [1, 6, 2], [1, 6, 8], [1, 6, 10], [1, 6, 14], [1, 6, 15], [1, 7, 5], [1, 7, 9], [1, 7, 13], [1, 7, 14], [1, 11, 3], [1, 11, 5], [1, 11, 9], [1, 11, 10], [1, 11, 13], [1, 13, 3], [1, 13, 7], [1, 13, 8], [1, 13, 11], [1, 13, 15], [1, 15, 5], [1, 15, 6], [1, 15, 9], [1, 15, 13]
и так далее.

Я написал "легонечко изменить". Да, мои извинения, надо было дать бОльшее уточнение: делители 4 и 7 сохраняются в условиях задачи.
Дать подсказку?

Цитата
kitonum

Цитата
sergeyklykov
Можете ли вы (вдвоём) переформулировать (легонечко) условия для 1...15 так, что не будет ни одного решения? Возможно ли такое?

Конечно возможно. Например, если числа 4 и 7 заменить на числа 9 и 12. Или ещё проще проверить отсутствие решений, если оба числа взять одной чётности.

Редактировалось 1 раз(а). Последний 20.08.2026 08:56.