Сколькими различными способами можно переставить числа от 1 до 19 и затем выписать их все подряд без пробелов так, что в результате получится палиндром?

задан 21 Июл '17 16:57

1

Задача уже долго "висит". Тут в целом всё было понятно почти сразу, но без бумаги трудно было точно всё сосчитать. Сейчас, вроде бы, ответ стал понятен, так что сегодня вечером попробую написать.

(27 Июл '17 12:42) falcao
10|600 символов нужно символов осталось
1

Подсчитаем число палиндромов, составленных из знаков различных чисел от 1 до 19.

Будем принимать во внимание следующее:

  • длина палиндрома равна 29;
  • символы в позициях 14, 15, 16 соответственно равны 1, 0, 1;
  • в левой части (на позициях от 1 до 14) содержится 6 символов «1» и по одному символу $% x \in X=\{2, \dots 9\}. $%

Обозначим $% z=(z_1, \dots , z_{14}), $% где либо $% z=1, $% либо $% z=x $% – в соответствии с символами палиндрома. Очевидны свойства допустимой последовательности $% z: $%

  • C1. $% z_{14}=1.$%
  • C2. В последовательности $% z $% не более двух подряд следующих символов $% x.$%
  • C3. Последовательность $% z $% не содержит подпоследовательность $% (x,x,1,1,x,x)$%. $%
  • C4. Из двух подряд следующих символов $% x $% в последовательности $% z $% первый символ соответствует второму знаку числа $% (1,x)$%, а второй - однозначному числу $% (x). $%
  • C5. $% z_2=1. $%

В рамках перечисленных свойств допустимы лишь следующие последовательности:

$% z^1=(x,1,x,1,1,x,x,1,x,x,1,x,x,1), $% $% z^2=(x,1,x,x,1,x,1,1,x,x,1,x,x,1), $% $% z^3=(x,1,x,x,1,x,x,1,x,1,1,x,x,1), $% $% z^4=(x,1,x,x,1,x,x,1,x,x,1,x,1,1), $% $% z^5=(1,1,x,x,1,x,x,1,x,x,1,x,x,1), $%

$% z^6=(x,1,1,x,1,x,x,1,x,x,1,x,x,1), $% $% z^7=(x,1,x,x,1,1,x,1,x,x,1,x,x,1), $% $% z^8=(x,1,x,x,1,x,x,1,1,x,1,x,x,1), $% $% z^9=(x,1,x,x,1,x,x,1,x,x,1,1,x,1), $%

причем $% z^1, \dots, z^5 $% содержат число 1 и не содержат 11, а $% z^6, \dots, z^9 $% – наоборот.

Важно отметить, что каждая из последовательностей $% z^i$% допускает единственный вариант расположения однозначных и двузначных чисел. Так, для последовательности $% z^1 $% таким вариантом является:

$% (z_1), (1, z_3), 1, (1, z_6), (z_7), (1,z_9), (z_{10}), (1, z_{12}), z_{13}, 10, $% $% (1, z_{13}), (z_{12}), (1,z_{10}), (z_9), (1, z_7), (z_6), 11, (z_3), (1,z_1), $%

а для последовательности $% z^6=(x,1,1,x,1,x,x,1,x,x,1,x,x,1) $% эти числа равны:

$% (z_1), 11, (z_4), (1,z_6), (z_7), (1,z_9), (z_{10}), (1,z_{12}), (z_{13}), 10,$% $% (1,z_{13}), (z_{12}), (1, z_{10}), (z_9), (1,z_7), (z_6), (1, z_4), 1, (1, z_1), $%

где $% z_j \in X. $%.

Аналогично единственность вариантов расположения однозначных и двузначных чисел устанавливается для других последовательностей $% z^i. $%

С другой стороны, при любой расстановке различных символов 2, 3, ..., 9 в последовательностях $% z^i, i=1, \dots ,8, $% в позициях $% z_j=x $% последовательность $% z^i $% дает палиндром.

Примерами палиндромов, построенных на базе последовательностей $% z^1, z^6,$% являются следующие

$% P^1=2, 13, 1, 14, 5, 16, 7, 18, 19, 10, 19, 8, 17, 6, 15, 4, 11, 3, 12, $%

$% P^6=2, 11, 3, 14, 5, 16, 7,18, 9, 10,19,8, 17, 6, 15, 4, 13, 1,12 $%

(в позициях $% z_j=x $% цифры записаны по порядку).

Таким образом, число палиндромов, составленных из знаков различных чисел от 1 до 19,, равно $% N=9\cdot 8! =9!. $% Учитывая, что каждому такому палиндрому соответствует единственная перестановка чисел $% 1, \dots, 19, $% это число $% N $% дает ответ на вопрос задачи.

ссылка

отвечен 29 Июл '17 19:00

изменен 29 Июл '17 23:57

@Urt: я так пока и не нашёл свободного времени, будучи в поездке, но у меня ответ не такой получился! Так что надо будет написать и сравнить.

(29 Июл '17 19:58) falcao

@falcao, мне показалось все прозрачным, но постараюсь тщательно проверить. Очень интересно посмотреть Ваше решение.

(29 Июл '17 20:13) Urt

@falcao, нашел погрешность - неверно сформулировано свойство 3. Там должно быть отражено лишь условие, что (1,1) не могут с двух сторон окружаться (x,x). Тогда допустимых последовательностей возможно будет больше (?). Буду решение корректировать, но новых вариантов пока не нашел.

(29 Июл '17 20:45) Urt

@Urt: я при беглом просмотре также усомнился в справедливости пункта C3. У меня "пилотной" версией ответа было 17*8!, но в процессе написания решения оказалось, что я это число завысил, а вместо 17 = 1 + дважды восемь там должно быть 9 = 1 + дважды четыре. То есть мой ответ 9!.

(29 Июл '17 21:24) falcao

@falcao, справедливость С3, как будто, следует из недопустимости (xx11xx). Так, для последовательности с началом x11xx1 в любом случае получим, что второй символ – число (иначе четвертый будет числом в левой и правой частях). Но при этом первый символ будет числом в левой и правой частях.

По Вашему решению есть вопрос - сформулирую после более глубокого осмысления.

(29 Июл '17 22:28) Urt

@Urt: а что если вставить t.11 и 1.1t в начало и конец для a.1b.c.1d.e.1f.g.10.1g.f.1e.d.1c.b.1a?

(29 Июл '17 22:32) falcao

@falcao, этот вариант учтен в последовательности $% z^5=(x11x1xx1xx1xx1) $% (без запятых).

(29 Июл '17 23:00) Urt

@falcao, оказалась неучтенной последовательность $% z^9=(11xx1xx1xx1xx1).$% Тогда действительно N=9! Сейчас буду править решение.

(29 Июл '17 23:38) Urt
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
1

У меня в ответе получилось 9!=362880.

Всего цифр в числе 29, среди них 0 встречается один раз. Остальные цифры встречаются либо дважды (от 2 до 9), либо 12 раз (цифра 1). Поэтому 0 находится посередине, являясь частью числа 10. За ним идёт цифра 1, которая является или частью числа вида 1x (строчные латинские буквы будут обозначать цифры от 2 до 9), или частью числа 11. Покажем, что эта цифра не может являть собой число 1.

Либо слева, либо справа от нуля идёт число 11. В первом случае симметричные им цифры -- это сочетание числа 1 и первой цифры числа 1x. То есть слева идут x и 11, справа симметрично им идут 1 и 1x. Во втором случае числу 11 правее нуля соответствуют 1 и 1x, то есть слева идут 1 и 1x. В любом случае, число 1 симметрично цифре числа 11.

Теперь пусть после 10 идёт 11. Тогда в середине идут 1.10.11. Вокруг этой конфигурации слева должны идти x.1y, а справа y.1x. Далее всё "обрамляется" тройками такого же вида, и всё задаётся порядком следования цифр от 2 до 9. Пример:

2.13.4.15.6.17.8.19.1.10.11.9.18.7.16.5.14.3.12

и после перестановки цифр получается 8! вариантов.

Теперь пусть после 10 идёт не 11, а 1x. В середине будет x.10.1x. Далее слева и справа всё "обрамляется" тройками вида y.1z, z.1y; всего три таких пары. В каком-то месте должно идти или t.11 слева, 1.1t справа, или наоборот. Если временно исключить эти симметричные тройки цифр, то получится палиндром типа a.1b.c.1d.e.1f.g.10.1g.f.1e.d.1c.b.1a, и вернуть извлечённую пару на место можно 8 способами -- четыре способа выбрать место вставки, умноженное на два варианта типа слева/справа. Итого с учётом перестановки цифр происходит умножение на 8!, и дополнительно оказывается ещё 8*8! палиндромов. Итого 9! чисел.

ссылка

отвечен 29 Июл '17 21:19

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

(30 Июл '17 0:39) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

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

задан
21 Июл '17 16:57

показан
623 раза

обновлен
30 Июл '17 0:39

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

по почте:

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

по RSS:

Ответы

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

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