Форум » Кодирование и декодирование информации » N Задание 10 N 117 (К. Поляков) » Ответить
N Задание 10 N 117 (К. Поляков)
tla: 117) Петя составляет шестибуквенные слова перестановкой букв слова КАБАЛА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя? Мое решение: 1) если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6! = 720 2) так как перестановка одинаковых букв не даёт нового слова, 3 одинаковых буквы уменьшают количество уникальных слов в 3 раза; оно равно 720/3 = 240 3) теперь нужно вычесть количество слов, где встречаются ААА; обозначим Y=ААА, таким образом, нужно найти количество слов из 4-х разных «букв» (К, Б, Л, Y), это количество равно 4! = 24 4) теперь подсчитаем слова, в которых есть X=АА, получаем набор из 5 «букв» (А, К, Б, Л, Х), количество слов равно 5! = 120 5) количество нужных нам слов равно 240 – 24 – 120 = 96. 6) В Ответе: 24. Где я ошибаюсь?
Ответов - 4
tla: Рассуждения 3 и 4 можно упростить: 3-4) подсчитаем слова, в которых есть X=АА, получаем набор из 5 «букв» (А, К, Б, Л, Х), количество слов равно 5! = 120. Среди них есть слова, в которых есть ААА, но нам их все равно нужно вычитать. То есть имеем 120, где есть АА, в том числе и ААА 5) количество нужных нам слов равно 240 – 120 = 120.
tla: Где ошибка?
polyakovss: Здравствуйте, tla! Эта задача решена здесь (polyakovss Сообщение: 166).
polyakovss: Как уже было сказано, задача 117 решена здесь (polyakovss Сообщение: 166). А здесь рассмотрим предложенный участницей tla метод решения и проведем работу над ошибками. tla пишет: Где ошибка?так как перестановка одинаковых букв не даёт нового слова, 3 одинаковые буквы уменьшают количество уникальных слов в 3 раза; оно равно 720/3 = 240 Нет. 3 одинаковые буквы уменьшают количество уникальных слов в 3! раз; оно равно 720/3! = 720/6 = 120. Это следует из формулы для перестановок с повторениями: (3+1+1+1)!/(3!*1!*1!*1!). Таким образом, общее количество перестановок букв слова КАБАЛА равно 120. количество слов, где встречаются ААА; обозначим Y=ААА, таким образом, нужно найти количество слов из 4-х разных «букв» (К, Б, Л, Y), это количество равно 4! = 24 Это правильно. подсчитаем слова, в которых есть X=АА, получаем набор из 5 «букв» (А, К, Б, Л, Х), количество слов равно 5! = 120 Это так. Вопрос лишь в том, какие это слова! Если AX или XA стоят рядом, то это даст удвоенное количество слов, где встречаются ААА, то есть 24*2 = 48. Остальные 120 - 48 = 72 соответствуют словам, где АА и А не стоят рядом. Количество перестановок букв слова КАБАЛА, не содержащих слов с двумя подряд одинаковыми буквами = (общее количество перестановок) - (количество слов, где встречаются ААА,) - (количество слов, где АА и А не стоят рядом) = 120 - 24 - 72 = 24. Ответ: 24. Рассуждения 3 и 4 можно упростить: 3-4) подсчитаем слова, в которых есть X=АА, получаем набор из 5 «букв» (А, К, Б, Л, Х), количество слов равно 5! = 120. Среди них есть слова, в которых есть ААА, но нам их все равно нужно вычитать. То есть имеем 120, где есть АА, в том числе и ААА 5) количество нужных нам слов равно 240 – 120 = 120. Обратим внимание: Среди них есть слова, в которых есть ААА, но нам их все равно нужно вычитать. Как уже было показано, при таком методе решения в 120 входит удвоенное количество слов, где встречаются ААА. Поэтому лишнее (24) нужно из 120 вычесть: 120 - 24 = 96. Искомое количество равно (общее количество перестановок) - (количество слов, где встречаются ААА, и где АА и А не стоят рядом) = 120 - 96 = 24. Ответ: 24.
полная версия страницы