РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 10268 Добавить в вариант

Найдите количество десятибуквенных «слов», составленных из букв А, Б, В (под «словом» понимается любая последовательность подряд идущих букв) таких, что в них есть не более трёх букв Б.

Спрятать решение

Решение.

Пусть нужно посчитать количество «слов» из n букв. Если букв Б нет, то на каждую позицию можно выбрать одну из двух букв  — получаем 2ⁿ слов. Если буква Б одна, то сначала есть n способов её разместить, после чего на оставшиеся позиции есть по два варианта  — выходит $n умножить на 2 в степени левая круглая скобка n минус 1 правая круглая скобка$ слов. Если две буквы Б, то есть $C_n в квадрате$ способа их разместить, а затем $2 в степени левая круглая скобка n минус 2 правая круглая скобка$ способов выбрать остальные буквы  — т. е. $n левая круглая скобка n минус 1 правая круглая скобка умножить на 2 в степени левая круглая скобка n минус 3 правая круглая скобка$ слов. Аналогично для трёх букв Б получаем $C_n в кубе умножить на 2 в степени левая круглая скобка n минус 3 правая круглая скобка$ слов. В итоге есть

$2 в степени n плюс 2 в степени левая круглая скобка n минус 1 правая круглая скобка умножить на C_n в степени 1 плюс 2 в степени левая круглая скобка n минус 2 правая круглая скобка умножить на C_n в квадрате плюс 2 в степени левая круглая скобка n минус 3 правая круглая скобка умножить на C_n в кубе$

слов. Если n  =  10, то это число равно 33024.

Ответ: 33024.

Замечание. Если считать, что каждая из букв А, Б, В должна встретиться в «слове хотя бы один раз, то получим $n левая круглая скобка 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 2 правая круглая скобка$ случаев с одной буквой Б: n способов выбора места для буквы Б; $2 в степени левая круглая скобка n минус 1 правая круглая скобка$ способов выбора букв на оставшиеся места, из которых не подходят ровно два (все буквы А или все буквы В); $C_n в квадрате левая круглая скобка 2 в степени левая круглая скобка n минус 2 правая круглая скобка минус 2 правая круглая скобка$ случаев с двумя буквами Б; $C_n в кубе левая круглая скобка 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 2 правая круглая скобка$ случаев с тремя буквами Б. В сумме выходит

$n левая круглая скобка 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 2 правая круглая скобка плюс дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби левая круглая скобка 2 в степени левая круглая скобка n минус 2 правая круглая скобка минус 2 правая круглая скобка плюс дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка левая круглая скобка n минус 2 правая круглая скобка , знаменатель: 6 конец дроби левая круглая скобка 2 в степени левая круглая скобка n минус 3 правая круглая скобка минус 2 правая круглая скобка$

способов.

Олимпиада школьников Физтех, 10 класс, 1 тур (отборочный), 2024 год

Классификатор: Комбинаторика, вероятность, статистика. Размещения, перестановки и сочетания

Спрятать решение · Помощь