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

задан 26 Сен '17 16:06

10|600 символов нужно символов осталось
2

При n=2 расстановка невозможна, при n=3 тоже (2 не с чем поставить рядом). При n=4 подходит 2413. Далее при появлении очередного числа его всегда будет куда поставить: 5 налево, 6 направо, 7 налево, 8 направо, и так далее.

В таком виде оно смотрится слишком уж просто. Наверное, имеет смысл ставить задачу о числе вариантов для каждого n. Тогда, скорее всего, всё тоже как-то должно анализироваться.

ссылка

отвечен 26 Сен '17 18:31

1

@falcao, большое Вам спасибо от меня и от Аллки! А задача, Вы не поверите, предлагалась на австралийской математической олимпиаде сего года :) Мы с Аллкой её условие просто с инглиша перевели, не впервой. Аллка домой придет и ссылку на оригинальный текст условия даст, я с мобильника не могу...

(26 Сен '17 20:38) Пацнехенчик ...
1

@Пацнехенчик ...: подсчёт количества вариантов для каждого n -- задача весьма интригующая. Я пока не знаю, имеет ли смысл её оформлять в качестве отдельного вопроса, так как не могу оценить уровень сложности. Но вычисления показывают, что закономерность там как минимум странная. Начиная с n=4, количество вариантов оказывается таким: 2, 10, 12, 8, 12, 30. Последнее число для n=9 меня, скажем так, "убило" :) Интересно, что там дальше? Тупой перебор всех n! вариантов там уже смотрится плохо, но можно модифицировать алгоритм.

(26 Сен '17 21:45) falcao
1

Следующее число (для n=10) -- о ужас -- равно 72. Это машина у меня 10! вариантов перебрала :)

(26 Сен '17 22:42) falcao
1

Оказывается, эта последовательность известна, и числа там активно растут. Видимо, проклассифицировать не удастся, а я надеялся на то, что примеры там все укладываются в какое-нибудь несложное правило.

Ссылка

(26 Сен '17 22:52) falcao

@falcao, а вот и обещанная @Пацнехенчик ...ом ссылка: http://www.amt.edu.au/wp-content/uploads/2017-AMO-Solutions.pdf Там самый первый задач как раз и есть он самый :)

(27 Сен '17 0:13) Аллочка Шакед

@Аллочка Шакед: да, спасибо. Они там как-то перемудрили с индуктивными конструкциями. Ведь приписывать то справа, то слева -- это совсем просто.

А меня заинтересовал циклический вариант той же задачи. Имеются в виду числа на окружности, а расстояние измеряется как обычно. Там для n=5 есть цикл 13524, и все "линейные" решения получаются из него. Потом снова какое-то время ничего нет, а при n>=10 примеры строятся. Интересно!

(27 Сен '17 0:30) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×310

задан
26 Сен '17 16:06

показан
254 раза

обновлен
27 Сен '17 0:30

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

по почте:

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

по RSS:

Ответы

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

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