Кузнечик прыгает по точкам с координатами 0 1 … 9 на координатной прямой и посещает каждую точку только один раз(кроме нуля). Он начинает с нуля и возвращается на ноль. Найти максимальную длину пути и количество способов проделать этот путь.

задан 24 Сен '17 14:33

изменен 24 Сен '17 14:35

@nynko: по-моему, на форуме уже была похожего содержания задача, но там в лучшем случае требовалось найти максимальную длину. Правда, я не помню ни ссылки, ни идеи решения. Гипотетический ответ есть, но вот подсчёт числа оптимальных траекторий пока что требует отдельного продумывания.

(24 Сен '17 16:57) falcao

@falcao. Я думаю, максимальная длина в районе 26-28, максимум 30. А число траекторий не должно быть большим. В этой задаче некуда особенно развернуться

(24 Сен '17 17:45) nynko

@nynko: почему такая маленькая длина? Возьмём траекторию 0918273645. Там получается 50.

(24 Сен '17 17:53) falcao

@falcao. Действительно...

(24 Сен '17 19:55) nynko

@nynko: тут нужно сначала найти удобный критерий оптимальности пути -- чтобы понятно было, что подсчитывать. Трудность в том, что оптимальные пути могут быть совсем непохожими. Например: 051423 (с той же закономерностью, что и выше) имеет длину 18. С другой стороны, путь 031524 имеет такую же длину, хотя он совсем не похож на предыдущий.

(24 Сен '17 20:27) falcao
10|600 символов нужно символов осталось
0

Для начала пусть будет сам подсчёт максимальной длины. По ходу дела получится и критерий оптимальности. Я сейчас вспомнил другую задачу на эту тему -- возможно, @EdwardTurJ укажет ссылку.

Будем решать равноценную задачу, где дана перестановка чисел $%x_1,...,x_n$% от $%1$% до $%n$%. Требуется максимизировать величину $%|x_1-x_2|+|x_2-x_3|+\cdots+|x_n-x_1|$%. Раскроем все модули. Получится сумма каких-то $%n$% чисел, минус сумма ещё $%n$% чисел. Она будет максимальной, если в первой группе собраны самые большие числа, а во второй самые маленькие. При этом одно и то же число может встречаться не более двух раз.

При чётном $%n=2k$% берём дважды числа большей половины во первую группу, и числа меньшей половины во вторую -- каждое по два раза. Это даёт $%2(2k+(2k-1)+\cdots+(k+1))-2(k+\cdots+1)=2k^2$% в результате почленного вычитания.

При нечётном $%n=2k+1$% поступаем аналогично, где среднее число $%k+1$% попадает в обе группы по разу. Получается разность $%2(2k+1+\cdots+k+2)-2(k+\cdots+1)=2k(k+1)$%. Единый ответ даётся формулой $%[\frac{n^2}2]$% (что косвенно указывает на естественность рассмотрения чисел от единицы, а не от нуля).

Теперь извлекаем критерий. Числа "большей" группы должны быть окружены числами "меньшей" -- именно тогда раскрытие модулей даёт требуемый результат. Понятно также, что такие примеры существуют -- достаточно взять $%1,n,2,n-1,...$%.

При чётном $%n=2k$% ставим все числа одной половины на чётные места, числа другой половины на нечётные. Понятно, что будет $%2k!^2$% вариантов, если всё равно, с чего начинать. Если же начинать с единицы (как было раньше с нуля), то надо поделить на $%2k$%, получая $%(k-1)!k!$%.

Для нечётного $%n=2k+1$% всё почти то же самое, но "среднее" число $%k+1$% должно находиться между меньшим и большим. Если его вычеркнуть, то получится конфигурация для чётного случая, а вставить можно далее в любое из $%2k+1$% мест. Но теперь, если начинать с единицы, то на это же число придётся поделить, что даст $%2k!^2$%.

Единый вид выражения выписать в принципе можно, но он будет плохо смотреться.

ссылка

отвечен 24 Сен '17 21:44

@falcao? спасибо. буду вникать

(25 Сен '17 21:24) nynko
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×309
×150

задан
24 Сен '17 14:33

показан
295 раз

обновлен
25 Сен '17 21:24

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

по почте:

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

по RSS:

Ответы

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

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