Расставьте в ряд числа 1,2,3,4,5,6,7,8,9,10 так, чтобы каждое число было делителем суммы всех предыдущих чисел (первое число должно без остатка делиться на второе, сумма первых двух- на третье, сумма первых трех- на четвертое, и.т.д.)

У меня получилось так: 10 2 6 3 7 4 8 5 9 1. А у авторов: Решение .Годится пример 10-2-4-8-3-9-6-7-1-5.

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

задан 18 Июл '17 1:42

1

Я уже отписал вам на Dxdy.

(18 Июл '17 2:14) Williams Wol...
10|600 символов нужно символов осталось
2

Сейчас, сидя на Казанском вокзале и ожидая поезда, от нечего делать написал программу в Maple. Чтобы не думать, выбрал наиболее "дубовый" алгоритм, но он сработал мгновенно и выдал 22 варианта:

[6, 1, 7, 2, 8, 3, 9, 4, 10, 5], [6, 2, 1, 9, 3, 7, 4, 8, 10, 5], [6, 2, 8, 4, 10, 5, 7, 3, 9, 1], [6, 3, 9, 2, 1, 7, 4, 8, 10, 5],

[7, 1, 4, 6, 9, 3, 2, 8, 10, 5], [7, 1, 4, 6, 9, 3, 10, 8, 2, 5], [7, 1, 8, 2, 6, 3, 9, 4, 10, 5], [7, 1, 8, 2, 9, 3, 6, 4, 10, 5],

[7, 1, 8, 4, 10, 6, 9, 3, 2, 5], [8, 1, 9, 3, 7, 2, 6, 4, 10, 5], [8, 2, 10, 4, 3, 9, 6, 7, 1, 5], [8, 2, 10, 4, 6, 5, 7, 3, 9, 1],

[8, 4, 2, 7, 3, 6, 10, 5, 9, 1], [8, 4, 6, 2, 10, 5, 7, 3, 9, 1], [8, 4, 6, 3, 7, 2, 10, 5, 9, 1], [8, 4, 6, 9, 3, 10, 2, 7, 1, 5],

[9, 1, 2, 6, 3, 7, 4, 8, 10, 5], [9, 3, 4, 8, 6, 10, 2, 7, 1, 5], [9, 3, 6, 2, 1, 7, 4, 8, 10, 5], [10, 2, 4, 8, 3, 9, 6, 7, 1, 5],

[10, 2, 4, 8, 6, 5, 7, 3, 9, 1], [10, 2, 6, 3, 7, 4, 8, 5, 9, 1].

Интересно, что Ваш вариант оказался последним в списке :) Он, видимо, лексикографически максимальный. Авторский -- третий с конца, но Ваш более логичен в этом смысле.

И ещё интересно, что никакого перебора 10! вариантов тут нет, а то было бы медленно: программа проверяет всё с самого начала, и если оно не подходит, то дальше она этот вариант не продолжает.

ссылка

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

2

На альтернативном форуме придумали очень крутой алгоритм, который находит случайный пример за sqrt(n)n, где N - длина массива. Идея такая: Что последнее число, должно делится на n(n+1)/2, предпоследнее должно делится на n(n+1)/2-последнее и так далее.

(18 Июл '17 23:25) Williams Wol...

@falcao, большое спасибо! Ах, Казанский вокзал! Моя нога не ступала там уже 26 лет :)

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

@Williams Wol...: припоминаю какую-то задачу с похожим сюжетом. Интересно было бы этим способом просчитать данный пример вручную, без компьютера. Пока не ясно, получится ли. Скажем, сразу ясно, что в конце либо 1, либо 5, но дальше начинаются "ветвления".

@Аллочка Шакед: произведя несложное действие по вычитанию, поймал себя на мысли, что очень многие мои знакомые и коллеги именно в этом году уехали -- в разные места.

(21 Июл '17 13:01) falcao
1

А вы попробуйте этим алгоритмом, если все очень быстро считать, то произвольный пример построить можно очень быстро. (не более двух минут)

(21 Июл '17 16:55) Williams Wol...
1

@Williams Wol...: я думаю, что само по себе построение какого-нибудь примера -- это не проблема, но большую ценность представляет подсчёт общего числа вариантов. Правда, я пока не уверен в том, что это легко осуществить.

(21 Июл '17 20:17) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

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

задан
18 Июл '17 1:42

показан
894 раза

обновлен
21 Июл '17 20:17

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

по почте:

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

по RSS:

Ответы

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

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