Задание 8 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Алфавитная нумерация слов

Все шестибуквенные слова, составленные из букв Т, Е, О, Р, И, Я, записаны в алфавитном порядке и пронумерованы. Определите, под каким номером в этом списке стоит первое слово с чётным номером…

1. 1
   В алфавитном порядке буквы расположены так: Е, И, О, Р, Т, Я. Слова, начинающиеся с Е и И, занимают первые два блока по $6^5$ слов. Первое подходящее начало слова — О.$$2 \cdot 6^5 + 1 = 15553$$
2. 2
   Чтобы слово с началом О содержало не менее двух букв Р и было первым в алфавитном порядке, выбираем минимальные возможные буквы в первых позициях и ставим Р в последние две позиции: ОЕЕЕРР.$$3 \cdot 6 + 3 = 21$$

Ещё 2 шага — в полном решении

Подсчёт слов с ограничениями

Все пятибуквенные слова, составленные из букв А, Л, Г, О, Р, И, Т, М, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ААААА 2. ААААГ 3. ААААИ 4. ААААЛ 5. ААААМ 6. ААААО 7. ААААР…

1. 1
   В алфавите 8 букв. При нумерации слов номер слова равен единице, прибавленной к числу, записанному цифрами с номерами букв в восьмеричной системе. Поэтому чётному номеру соответствует нечётная последняя цифра.
2. 2
   Нечётные номера имеют буквы Г, Л, О, Т. Значит, последняя буква может быть выбрана 4 способами.

Ещё 3 шага — в полном решении

Подсчёт чётных номеров слов

Все шестибуквенные слова, составленные из букв П, Я, Т, Н, И, Ц, А, записаны в алфавитном порядке и пронумерованы. В начале списка: 1. АААААА; 2. АААААИ; 3. АААААН; 4. АААААП; 5. АААААТ; 6. АААААЦ…

1. 1
   Алфавитный порядок букв: А, И, Н, П, Т, Ц, Я. Им соответствуют цифры 0, 1, 2, 3, 4, 5, 6 в семеричной системе счисления. Номер слова на единицу больше значения соответствующего шестизначного числа.
2. 2
   Так как основание системы счисления 7 нечётное, чётность значения числа определяется чётностью суммы его цифр. Буква Я имеет индекс 6 и на чётность не влияет. Среди индексов 0–5 три чётных и три нечётных.

Ещё 3 шага — в полном решении

Количество кодовых слов

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

1. 1
   Единственная гласная занимает одну из пяти позиций, а выбрать её можно двумя способами: Э или А.$$5 \cdot 2$$
2. 2
   На оставшихся четырёх позициях могут находиться согласные Т или Н, независимо друг от друга.$$2^4$$

Ещё 1 шаг — в полном решении

Номер слова в алфавитном списке

Все 3-буквенные слова, составленные из букв Е, И, К, Н, У, Ч, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером в списке идёт первое слово, которое начинается с буквы Н?

1. 1
   В алфавитном порядке перед буквой Н находятся буквы Е, И и К.
2. 2
   Для каждой фиксированной первой буквы две оставшиеся позиции можно заполнить 6 способами каждая, поэтому количество слов равно $6^2 = 36$.

Ещё 2 шага — в полном решении

Подсчёт допустимых слов

Вася составляет 6-буквенные слова, в которых могут быть использованы только буквы В, И, Ш, Н, Я, причём буква В используется не более одного раза. Каждая из других допустимых букв может встречаться…

1. 1
   Сначала рассмотрим слова без буквы В. На первую позицию можно поставить И, Н или Я — 3 варианта. На позиции со второй по пятую можно поставить любую из четырёх букв И, Ш, Н, Я. Последняя буква должна быть согласной: Ш или Н.$$3 \cdot 4^4 \cdot 2 = 1536$$
2. 2
   Теперь рассмотрим слова, в которых буква В встречается ровно один раз и стоит на первой позиции. Остальные четыре позиции перед последней заполняются четырьмя буквами, а последняя буква выбирается двумя способами.$$4^4 \cdot 2 = 512$$

Ещё 3 шага — в полном решении

Максимальный и минимальный путь

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз. Между соседними клетками могут быть…

1. 1
   Вычислим максимальные суммы для маршрутов до клеток таблицы. В правой нижней клетке получаем:$$1 \to 9 \to 17 \to 21;\quad 11 \to 20 \to 21 \to 24;\quad 12 \to 23 \to 35 \to 37;\quad 14 \to 26 \to 40 \to 46$$
2. 2
   Аналогично вычислим минимальные суммы. В правой нижней клетке минимальная сумма равна:$$1 \to 9 \to 17 \to 21;\quad 11 \to 10 \to 11 \to 14;\quad 11 \to 13 \to 23 \to 16;\quad 13 \to 14 \to 18 \to 22$$

Первое слово на букву Н

Все 4-буквенные слова, в составе которых могут быть буквы С, Е, Н, О, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером в списке идёт первое слово, которое начинается с…

1. 1
   В алфавитном порядке буква Е идёт перед буквой Н, поэтому перед первым словом на Н расположены все слова, начинающиеся с Е.
2. 2
   После первой буквы в слове остаются три позиции. Каждую позицию можно заполнить одной из четырёх букв: С, Е, Н или О.$$4^3 = 64$$

Ещё 1 шаг — в полном решении

Первое слово на букву Л

Все четырёхбуквенные слова, в составе которых могут быть буквы А, В, Л, О, С, записаны в алфавитном порядке и пронумерованы начиная с 1. Под каким номером в списке идёт первое слово, которое…

1. 1
   В алфавите задачи пять букв: А, В, Л, О, С. До буквы Л идут две буквы: А и В.
2. 2
   Для каждого из двух первых символов оставшиеся три позиции можно заполнить пятью способами.$$2 \cdot 5^3 = 250$$

Ещё 1 шаг — в полном решении

Максимальная и минимальная сумма

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…

1. 1
   Считайте из электронной таблицы размеры квадрата, стоимости монет и сведения о стенах.
2. 2
   Для каждой клетки вычислите максимальную сумму пути из левой верхней клетки. Переходы разрешены только из верхней или левой клетки, если между клетками нет стены.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

Ещё 2 шага — в полном решении

Номер первого подходящего слова

Все шестибуквенные слова, составленные из букв А, П, Р, Е, Л, Ь, записаны в алфавитном порядке и пронумерованы. Определите, под каким номером в этом списке стоит первое слово с нечётным номером…

1. 1
   Буквы в алфавитном порядке имеют индексы: А — 0, Е — 1, Л — 2, П — 3, Р — 4, Ь — 5.
2. 2
   Слово не должно начинаться с А или Л. Чтобы получить первое возможное слово, выбираем минимальную допустимую первую букву Е.

Ещё 4 шага — в полном решении

Девятеричные числа с цифрами 8

Определите количество девятеричных шестизначных чисел, которые не начинаются с нечётных цифр, не оканчиваются цифрами 1 или 2, а также содержат не менее двух цифр 8.

1. 1
   Первая цифра должна быть чётной и ненулевой: $4$ варианта. Последняя цифра не может быть равна $1$ или $2$: $7$ вариантов. Остальные четыре цифры выбираются из девяти цифр.$$N=4\cdot 9^4\cdot 7=183708$$
2. 2
   Посчитаем числа без цифры $8$. Для первой цифры остаётся $3$ варианта, для каждой из четырёх средних цифр — по $8$ вариантов, для последней — $6$ вариантов.$$N_0=3\cdot 8^4\cdot 6=73728$$

Ещё 2 шага — в полном решении

Подсчёт чисел с ограничениями

Определите количество пятизначных чисел, записанных в девятеричной системе счисления, в записи которых ровно одна цифра 1, при этом никакая чётная цифра не стоит рядом с цифрой 1.

1. 1
   В девятеричной системе используются цифры от 0 до 8. Так как цифра 1 должна встречаться ровно один раз, на остальных позициях доступны 8 цифр. Рядом с цифрой 1 могут стоять только нечётные цифры 3, 5 и 7.
2. 2
   Если цифра 1 стоит на первой позиции, рядом с ней 3 варианта, а на трёх остальных позициях по 8 вариантов:$$3\cdot8\cdot8\cdot8=1536$$

Ещё 5 шагов — в полном решении

Номер слова в алфавитном списке

Все 4-буквенные слова, в составе которых могут быть только буквы А, И, О, У, Э, записаны в алфавитном порядке и пронумерованы. Под каким номером стоит слово ИЭУЭ?

1. 1
   Упорядочим буквы и сопоставим им номера, начиная с нуля: А — 0, И — 1, О — 2, У — 3, Э — 4.$$ИЭУЭ \rightarrow 1,4,3,4$$
2. 2
   Поскольку все слова имеют длину 4, их порядок совпадает с порядком четырёхзначных чисел в системе счисления с основанием 5.$$1 \cdot 5^3 + 4 \cdot 5^2 + 3 \cdot 5 + 4 = 244$$

Ещё 1 шаг — в полном решении

Первое слово по условиям

Все пятибуквенные слова, в составе которых могут быть только русские буквы А, Л, П, Ц, Я, записаны в алфавитном порядке и пронумерованы начиная с 1. Под каким номером в списке идёт первое слово…

1. 1
   В алфавитном порядке буквы имеют номера: А — 0, Л — 1, П — 2, Ц — 3, Я — 4. Так как буква Л запрещена, а слово должно содержать не более одной буквы А и ровно две буквы Ц, минимальное подходящее слово начинается с А.
2. 2
   После единственной буквы А выбираем минимальные допустимые буквы. До двух букв Ц можно поставить две буквы П, поэтому первое подходящее слово — АППЦЦ.$$АППЦЦ$$

Ещё 1 шаг — в полном решении

Последнее слово в списке

Все пятибуквенные слова, в составе которых могут быть только русские буквы Л, А, Й, М, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка. 1. ААААА 2. ААААЙ 3…

1. 1
   Буквы упорядочены так: А, Й, Л, М. Каждое пятибуквенное слово можно рассматривать как запись числа в системе счисления с основанием 4, где буквам соответствуют цифры 0, 1, 2, 3.
2. 2
   Чтобы получить последнее подходящее слово, первая буква должна быть М. После неё букву М использовать нельзя. Максимальное слово без соседних букв Л имеет вид МЛЙЛЙ.

Ещё 1 шаг — в полном решении

Цепочки из бусин

Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем месте — любая гласная, если первая буква согласная, и любая…

1. 1
   Средняя буква должна быть одной из M, O, S. Проверяем варианты: SMP, MSO и OSN подходят по этому условию, а SNO не подходит, так как в середине стоит N.
2. 2
   Первая буква должна быть одной из O, P, S и не совпадать со средней. Вариант SMP нарушает это условие: первая буква S совпадает со средней буквой M? Нет, но третья буква P должна быть гласной, так как первая буква S согласная. Поэтому…

Ещё 2 шага — в полном решении

Первое слово на У

Все 4-буквенные слова, в составе которых могут быть только буквы Л, Е, М, У, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка: 1. ЕЕЕЕ; 2. ЕЕЕЛ; 3. ЕЕЕМ…

1. 1
   В алфавитном порядке перед буквой У находятся четыре буквы: Е, Л, М и Р.$$4$$
2. 2
   Для каждого варианта первой буквы оставшиеся три позиции заполняются любыми из пяти букв.$$5^3 = 125$$

Ещё 1 шаг — в полном решении

Пятизначные числа разной чётности

Сколько существует десятичных пятизначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?

1. 1
   Так как рядом не могут стоять цифры одной чётности, возможны только две схемы чередования чётности.
2. 2
   Для схемы нечётная–чётная–нечётная–чётная–нечётная выбираем и размещаем три различные нечётные цифры и две различные чётные цифры:$$P_5^3 \cdot P_5^2 = (5 \cdot 4 \cdot 3)(5 \cdot 4) = 1200$$

Ещё 2 шага — в полном решении

Номер слова в списке

Все 6-буквенные слова, составленные из букв А, И, О, У, Э, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. АААААА; 2. АААААИ; 3. АААААО; 4. АААААУ. Под каким номером стоит слово…

1. 1
   Буквы упорядочены так: А, И, О, У, Э. Для третьей буквы И перед ней есть одна буква — А. После неё остаются три позиции, поэтому таких слов $1 \cdot 5^3$.$$1 \cdot 5^3 = 125$$
2. 2
   Для четвёртой буквы Э перед ней расположены четыре буквы, а после неё остаются две позиции.$$4 \cdot 5^2 = 100$$

Ещё 2 шага — в полном решении