2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ни на 3, ни на 5, ни на 7
Сообщение13.07.2017, 14:39 
Аватара пользователя


01/12/11

8634
(поначалу хотелось назвать задачу: "Нина, 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.

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

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение15.07.2017, 16:25 


08/09/13
210
Тут задача исчерпывается поиском для $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$, стояло число, меньшее чем хотя бы одно из этих чисел...

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение16.07.2017, 00:24 
Аватара пользователя


01/12/11

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

-- 16.07.2017, 00:27 --

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

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

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение16.07.2017, 00:38 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Ktina в сообщении #1233830 писал(а):
А можно разместить этот открытый и интересный вопрос в википедической статье об открытых математических проблемах?
Можно. Я разрешаю.
Если чуть серьёзнее: нужно ли?

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение16.07.2017, 10:00 
Аватара пользователя


01/12/11

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

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

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение16.07.2017, 22:02 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Проблема проблеме рознь.
Ну напишите, кто ж вам мешает-то. Хотите помощи, пришлите мне черновик ;-)

 Профиль  
                  
 
 Re: Ни на 3, ни на 5, ни на 7
Сообщение16.07.2017, 23:53 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group