Усложненная задача на перестановки букв в слове

Добрый день! Посчастливилось столкнуться с такой задачей:

"Cкoлькo paзличныx cлoв мoжнo cocтaвить из букв cлoвa «ЭKCЦEHTPИCИTET», ecли кaждoe cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT".

Возможно, задача может показаться простой и тривиальной, но в формулировке задачи заложено много подводных камней, которые делают процесс решения далеко не однозначным. Реально ли в данном случае проверить результат, смоделировав задачу на языке программирования или в матпакете?

0

Не вижу проблемы. Сначала найти кол-во перестановок, дающих подслово РИС, затем отдельно для ЦИНК, затем для ТЕСТ, Затем ЦИНК и РИС, РИС и ТЕСТ, ЦИНК и ТЕСТ, затем ЦИНК и ТЕСТ И РИС и метод включений-исключений подрубаем и получаем требуемое.

Добавлено через 40 секунд

Сообщение от agua заложено много подводных камней

Кстати где?

0

Сообщение от cmath Кстати где?

Они обнаружатся, если провести вычисления и затем проверить результат. Кстати, как его можно проверить в каком-нибудь матпакете типа Matlab или Mathematica? Само условие, на мой взгляд, неоднозначно и допускает несколько трактовок, и результаты, соответственно, будут разными. Поэтому я бы начал с построения какой-либо модели. Попробуйте сами провести выкладки и получить результат хотя бы для одного подслова РИС (т.е. слово содержит РИС и не содержит ни ЦИНК, ни ТЕСТ), и увидите, что все не так однозначно.

0

Сообщение от agua Попробуйте сами провести выкладки и получить результат хотя бы для одного подслова РИС (т.е. слово содержит РИС и не содержит ни ЦИНК, ни ТЕСТ), и увидите, что все не так однозначно.

Мда... Это тяжело... Пусть A - множество слов, содержащих РИС, B - ЦИНК, C - ТЕСТ. И РИС и ЦИНК содержат слова из , и РИС и ТЕСТ , все слова - , тогда кол-во слов, содержащих только РИС - . Все очень даже однозначно.

0

Сообщение от cmath Мда... Это тяжело...

Я с вами согласен – это действительно не так просто, как кажется, иначе я бы не стал размещать здесь эту задачу. Даже результаты вычисления можностей множеств A, B и C могут не совпасть с результатами проверки, отсюда и желание провести независимую экспертизу. Быстро набросать модель для проверки мне не удалось, поэтому я и обратился на форум. Попробуйте сами провести вычисления и проверить результат, если это у вас получится. Это обычная задача из сборника типовых расчетов, поэтому я тоже не ожидал от нее никаких подвохов.

0

Сложность заключается в повторяющихся буквах. Можно разобраться с ними. Сделать их "различными" - проще говоря присвоить некоторый индекс, например T₁, T₂, T₃ - искусственно ввести порядок, например ТЕСТ можно составить как Т₁ЕСТ₂ или Т₃ЕСТ₂ и т.д. Найти кол-во комбинаций, применить опять-таки принцип включений-исключений и уже на выходе исключить порядок (нужно будет разделить результат на 48=2!2!2!3!).

2

Сложности с повторяющимися буквами здесь как раз таки нет – нас не интересует, каким образом и из каких конкретно букв было составлено слово TECT (как Т₁ЕСТ₂ или как Т₃ЕСТ₂), потому что как только мы сформировали слово TECT (из любых подвернувшихся под руку букв), мы просто получили еще один атом – "метабукву" TECT, в дополнение к оставшимся 10 буквам, а потом просто применяем формулу перестановок с повторениями, учитывая парность букв И.

Сложность здесь в другом – она связана с повторяющимимся словами и касается именно слова TECT: оно может встречаться дважды в буквосочетании TECTECT (букв исходного слова для этого как раз достаточно) и как это сочетание обрабатывать (как одно слово, или как два) из условия задачи не ясно.

Подробнее: в условии сказано "кaждoe cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT", но что именно означает выражение "poвнo oднo из пoдcлoв", не уточнено, а в данной ситуации это важно. Например, сочетание TECTECT можно рассматривать как одно подслово TECT, встречающееся два раза, и какую бы трактовку мы ни приняли, это приводит к дополнительным сложностям при определении мощности множеств. Эти сложности, конечно, вполне разрешимы, но именно это (в том числе) и я назвал "подводным камнем" в условии задачи.

Второй подводный камень (с точки зрения добросовестного студента, решающего "сферическую задачу в вакууме" и не имеющего возможности уточнить условие) связан с тем, что не уточнено само понятие "слово", которое необходимо составлять из букв исходного слова ЭKCЦEHTPИCИTET, а именно: не сказано, сколько букв должно содержать это слово, т.е. должны быть использованы все 14 букв, или же слово PИC само по себе тоже подойдет – оно ведь не противоречит формулировке "cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT", т.к. содержит только слово PИC.

В виду присутствия этих "камней" в русле решения мне и пришла в голову мысль построить модель задачи и проверить результат честным перебором, но почему это не удалось сделать легко и быстро, думаю, понятно.

Спасибо за участие в обсуждении – мне хотелось получить свежий взгляд со стороны и проговорить все тонкие моменты вслух. Прием с нумерацией букв/слов вполне может пригоиться для разрешения коллизии со словом TECT, только немного в другом смысле.

0

Про "слова" видел специальную книжку, но, к сожалению, уже не вспомню автора и где её брал.
***
Обобщить задачу на слова с разным кол-вом букв можно, считать только долго и нудно. Можно впрочем попробовать.
***
Постановка задачи, по всей видимости, просто не корректна. А откуда такая проблема возникла?

0

Количество слов, имеющих в составе РИС, но не содержащих ни ЦИНК, ни ТЕСТ можно подсчитать так.
Рассматриваем все разные перестановки букв ЭKCЦEHTPИTET (от РИС оставляем только букву Р).
Таких слов 12!/(2!*3!), но среди них есть слова содержащие ЦИНК, их надо исключить.
Для этого считаем перестановки букв ЭCЦETPTET. Их 9!/(2!*3!)
А сколько слов содержат ТЕСТ? Для этого считаем перестановки букв ЭKCЦEHTPИ. Их 9!
А если ТЕСТ и ЦИНК содержатся одновременно, то слов будет столько, сколько перестановок ЭCЦETP, т.е. 6!
Итак, слов содержащих РИС, но не содержащих ни ЦИНК ни ТЕСТ ровно 12!/(2!*3!)-9!/(2!*3!)-9!+6!
Аналогично, можно посчитать и для оставшихся двух слов.

0

Сообщение от cmath Обобщить задачу на слова с разным кол-вом букв можно, считать только долго и нудно. Можно впрочем попробовать.

В этом необходимости нет – если задачу удастся решить для всех 14 букв, то потом просто останется рассмотреть по тому же алгоритму все остальные возможные сочетания из меньшего количества букв, т.е. это именно долго и нудно, но совсем не сложно (чисто бухгалтерская работа).

Сообщение от cmath Постановка задачи, по всей видимости, просто не корректна. А откуда такая проблема возникла?

Вот здесь соглашусь – вопросов к условию достаточно, и, как выясняется, не только самых очевидных. Не могу быть уверен, но не удивлюсь, если сам автор не предусмотрел особого случая со словом TECT, хотя это очень маловероятно, конечно. Сама задача взята из сборника типовых расчетов одного из технических вузов (название которого мы по понятным причинам здесь не будем упоминать всуе) и просто случайно подвернулась под руку. Никаких особых сложностей в ней не предполагалось.

TrueTerm, не могли бы вы, пожалуйста, рассчитать, сколько уникальных слов содержат слово TECT (наряду, возможно, с другими словами из списка), чтобы мы могли сравнить наши результаты.

0

cmath, TrueTerm, Байт (никого не забыл?), мне-таки удалось довести решение задачи до получения ответа в явном виде и проверить результат, построив компьютерную модель, но и первое, и второе далось ценой значительных усилий, т.к. задача по количеству нюансов и возможностей, которые необходимо учесть, чем-то напоминает сад расходящихся тропок Борхеса. Если кто-то располагает достаточным запасом времени и хочет проверить свои силы, можем сверить полученные результаты. В сборник типовых расчетов задача скорее всего попала по недосмотру составителя, т.к. больше похожа на мини-курсовую по теме "Формула включений–исключений".

Добавлено через 5 минут

Сообщение от TrueTerm Аналогично, можно посчитать и для оставшихся двух слов.

Конкретно вот этот вот пункт не совсем верен, хотя общий подход, конечно, правильный. Для слова РИС все подсчитано верно.

0