Ни на 3, ни на 5, ни на 7

[Ktina]

(поначалу хотелось назвать задачу: "Нина, 3! Нина, 5! Нина, 7!")

При каких натуральных $n>1$ можно расположить числа от 1 до $n$ по кругу так, что­бы сумма любых двух соседних чисел не делилась ни на 3, ни на 5, ни на 7?

У меня такое подозрение, что при любом $n>8$.
При меньших $n$ рядом с четвёркой должны двое стоять, а некому, а при ещё меньших (когда и четвёрки нет) единичка вынуждена стоять рядом с двойкой и их сумма кратна 3.

При $n=9$ возможна единственная (с точностью до...) расстановка: 317492658.
А затем можно пихать бОльшие числа в подходящие места. У меня с числами от 10 до 20 каждый раз получалось. В итоге, при $n=20$ получилась вот такая расстановка:
3 16 18 19 13 10 12 1 15 7 5 9 20 17 14 2 11 6 5 8.

Теперь бы доказать, что эта штука всегда работает...

[fractalon]

Тут задача исчерпывается поиском для $n < 2 \cdot 3 \cdot 5 \cdot 7 = 210$, а потом можно дублировать по модулю $105$. То есть берём последовательность для $n=105$, дублируем $\lfloor{\frac{n}{105}}\rfloor$ с прибавлением $105$ каждый раз, доклеивая сбоку к тому, что есть, а последующие числа добавляем в один из дублированных отрезков так же как мы добавляли бы их если бы дело происходило при $n \in [105;210]$.
А до 210 на компьютере я всё проверил, поочерёдно добавляя числа в случайные места из возможных - ни разу в тупик не попал. Вот перестановка для $n=210$

38, 48, 74, 20, 39, 53, 69, 23, 135, 134, 45, 107, 114, 14, 18, 26, 42, 86, 87, 41, 201, 137, 200, 72, 164, 174, 80, 132, 56, 78, 5, 24, 35, 54, 8, 81, 50, 3, 196, 202, 210, 181, 178, 166, 187, 136, 160, 193, 204, 184, 199, 133, 195, 151, 121, 157, 142, 154, 159, 130, 177, 127, 129, 115, 106, 186, 91, 138, 85, 124, 175, 99, 190, 94, 73, 148, 70, 82, 145, 61, 88, 75, 43, 51, 58, 105, 79, 150, 64, 60, 97, 111, 163, 46, 57, 169, 208, 40, 52, 205, 31, 93, 55, 123, 28, 34, 67, 126, 100, 84, 37, 172, 147, 76, 30, 16, 156, 25, 13, 139, 19, 27, 10, 33, 103, 1, 36, 22, 144, 109, 162, 112, 15, 7, 4, 189, 118, 49, 9, 209, 203, 206, 188, 191, 170, 176, 158, 168, 155, 192, 149, 197, 185, 143, 146, 165, 152, 171, 125, 131, 141, 140, 122, 119, 104, 182, 95, 183, 116, 120, 113, 96, 110, 207, 194, 179, 62, 102, 44, 92, 117, 32, 71, 101, 47, 89, 153, 59, 198, 128, 98, 83, 63, 29, 77, 167, 90, 161, 2, 66, 65, 6, 173, 180, 11, 12, 17, 21, 68, 108

-- 15.07.2017, 15:41 --

А вот для произвольного набора простых чисел вместо $\lbrace{3,5,7}\rbrace$ вопрос остаётся открытым и интересным...
Фактически чтобы избежать итеративного процесса нам нужно было найти перестановку чисел от $1$ до $210$ такую, чтобы между любыми двумя числами, сумма которых делится на $3$, $5$ или $7$, стояло число, меньшее чем хотя бы одно из этих чисел...

[Ktina]

fractalon
Большое спасибо!

-- 16.07.2017, 00:27 --

fractalon в сообщении #1233729 писал(а):

А вот для произвольного набора простых чисел вместо $\lbrace{3,5,7}\rbrace$ вопрос остаётся открытым и интересным...

А можно разместить этот открытый и интересный вопрос в википедической статье об открытых математических проблемах?

[Aritaborian]

Ktina в сообщении #1233830 писал(а):

А можно разместить этот открытый и интересный вопрос в википедической статье об открытых математических проблемах?

Можно. Я разрешаю.
Если чуть серьёзнее: нужно ли?

[Ktina]

Aritaborian в сообщении #1233833 писал(а):

нужно ли?

Дык открытая ж проблема?!

[Aritaborian]

Проблема проблеме рознь.
Ну напишите, кто ж вам мешает-то. Хотите помощи, пришлите мне черновик ;-)

[fractalon]

Ну мне не кажется этот вопрос таким уж сложным. Думаю, на форуме вполне могут найтись люди, способные это решить...