Комбинаторные задачи в ЕГЭ

Комбинаторные методы в ЕГЭ по информатике применяются для решения задачи №10 (бывшая В4). Рассмотрим решение типичных задач, с использованием комбинаторных приемов.

Решим задачу под номером В4 из демонстрационной версии ЕГЭ по информатике 2014 года.

Задача. Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет – один сигнал; в каком порядке идут цвета – существенно. Какое количество различных сигналов можно передать при помощи запуска ровно пяти таких сигнальных ракет, если в запасе имеются ракеты трёх различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?

Решение.

Ракеты могут быть трех различных цветов, при этом в одной последовательности пять ракет. Значит, рассматривается выборка объема пять из трех элементов (n = 3, k = 5).

Определим комбинаторную схему. Два положения в условие задачи:

• «в каком порядке идут цвета – существенно»;
• «цвет ракет в последовательности может повторяться»;

указывают на то, что – это размещения с повторениями.

Ответ. 243

Решим задачу №10 из демоверсии ЕГЭ по информатике 2016 года.

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы П, И, Р, причём буква П появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Решение.

1) буква «П» появляется ровно 1 раз, значит она может находиться на одной из 5 позиций в слове.

2) буквы «И» и «Р» заполнят остальные 4 позиции. Рассмотрим выборки объема 4 из 2 элементов (k = 4, n = 2). Кодовые слова могут отличаться как порядком следования букв, так и составом, значит, комбинаторная схема – размещения с повторениями. Найдем число таких размещений:

3) применим правило произведения: 5 * 16 = 80

Ответ. 80

Типичная тренировочная задача №10 для подготовки к ЕГЭ по информатике.

Задача. Вася составляет 5-буквенные слова из четырехбуквенного алфавита {A, C, R, T}, причём буква А используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом, считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение.

1) пронумеруем позиции в слове, тогда варианты расположений букв «А» можно представить в качестве неупорядоченного выбора двух цифр из пяти. Значит, комбинаторная схема - сочетания без повторений

2) остальные допустимые символы будут занимать 3 позиции. Эти выборки объемом 3 из 3 элементов будут отличаться как порядком следования, так и набором символов. Очевидно, комбинаторная схема – размещения с повторениями.

3) применим правило произведения: 27 * 10 = 270

Ответ. 270