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

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

задан 13 Июл '17 15:39

1

Интересная задача -- такое впечатление, что для каждого следующего числа всегда легко найти место. Я для 20 составил другой пример, вставляя новое число по принципу "куда придётся".

Число 21 можно вставить между 20 и 17 для Вашего случая. И таких мест довольно много. Если составить граф, то он будет очень близок к условиям теоремы Дирака, где гамильтоновость получается сразу. Но коэффициент чуточку не дотягивает до нужного: валентность вершины близка к n/2, но капельку поменьше.

Можно, наверное, продолжить процесс, доведя его до 100 с чем-то, а потом "сыграть" на периодичности mod 105.

(14 Июл '17 2:45) falcao

@falcao, большое спасибо!

(14 Июл '17 15:49) Аллочка Шакед
10|600 символов нужно символов осталось
1

Для всех чисел вплоть до 200 ответ положительный — воспользовался перебором случайных перестановок с последующей попыткой «доведения до совершенства» каждой получаемой перестановки. Дальше — не знаю.

«Доведение до совершенства»: найти обмен элементов, уменьшающий количество нарушений в строчке чисел, применить его; и повторить всё это дело, пока повторяется. Поскольку число нарушений не больше числа элементов, время поиска ограничено кубической функцией от числа элементов (количество перебираемых обменов умножить на количество элементов). Правда, процедура может не найти существующий пример.

ссылка

отвечен 18 Июл '17 21:52

изменен 19 Июл '17 1:35

@abracadabra-..., большое спасибо!

(19 Июл '17 1:11) Аллочка Шакед

Не за что. Я, собственно, не ответил на ваш вопрос. Вопрос ведь про любые числа. А уже при числах в районах 200 программа начинает ощутимо подтормаживать (в районе пары секунд).

Кстати, я беру по 100 случайных перестановок, потому цифра 41 очень мало значит — спешил, потому не подумал. Так что я и убрал её из ответа. Правильнее было сказать: как минимум 41.

(19 Июл '17 1:44) abracadabra-...
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×128

задан
13 Июл '17 15:39

показан
537 раз

обновлен
19 Июл '17 1:44

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru