Задание 8. Системы счисления и комбинаторика. ЕГЭ 2024 по информатике
Средний процент выполнения: 85.3%
Ответом к заданию 8 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Саша составляет шестибуквенные слова, в которых есть только буквы А, М, О, К, Т и С, причём в каждом слове буква Т используется один или два раза и при этом может стоять только на первом или на втором местах, а буква О встречается в слове ровно 2 раза, на пятом и шестом месте. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Поскольку на двух последних позициях обязательно стоит буква О, там всегда ровно один вариант расстановки букв. Количество вариантов зависит только от первых 4-х символов. Дальше будем считать именно для 4-х символов.
Рассмотрим все варианты расстановки буквы Т:
1. Буква Т встречается ровно 2 раза на первом и втором месте. Тогда на 3 и 4 месте могут стоять только буквы А/М/К/С. 4·4 = 16 вариантов.
2. Буква Т встречается ровно 1 раз на первом месте. Тогда на 2, 3 и 4 месте могут стоять только буквы А/М/К/С. 4·4·4 = 64 варианта.
3. Буква Т встречается ровно 1 раз на втором месте. Тогда на 1, 3 и 4 месте могут стоять только буквы А/М/К/С. 4·4·4 = 64 варианта.
Всего вариантов: 64+64+16 = 144.
Ответ: 144
Задача 2
Саша составляет шестизначные числа, в которых есть только цифры 1, 2 и 3, причём цифра 1 используется в каждом числе не более двух раз и при этом может стоять только на первом или втором местах. Каждая из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
1) без цифры 1: 2*2*2*2*2*2=64
2) с одной 1 на первом месте: 1*2*2*2*2*2=32
3) с одной 1 на втором месте: 2*1*2*2*2*2=32
1) с двумя 1: 1*1*2*2*2*2=16
Итого: 64+32+32+16=144
Задача 3
Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква Г используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Количество перестановок букв Т на 5 позициях = 10. можно вычислить по формуле n!/(n-m)! где n — это количество позиций (в данном случае 5), а m — количество букв, которые необходимо расположить (в данном случае 2 буквы Т). по формуле получается 20, но у нас абсолютно одинаковые элементы (буквы Т) поэтому делим на факториал 2, чтобы не учитывать повторы.
На каждой из оставшихся трёх позиций в слове могут стоять по 5 букв — итого 125 комбинаций.
В итоге: для каждого из 10 вариантов расположения букв Т получается по 125 комбинаций оставшихся трёх букв: 10 * 125 = 1250.
Задача 4
Аня составляет 5-буквенные слова, в которых встречаются только буквы А, Б, В. Причем буква A может встречаться только первой или последней (двух букв А в слове быть не может), но при этом должна присутствовать обязательно. Каждая из других допустимых букв может встречаться в слове на любом месте или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Аня?
Решение
Поскольку буква А должна стоять либо на первом, либо на последнем месте (должна встретиться в слове, но не на обеих позициях), то получаем такие комбинации размещения букв:
A 2 2 2 2 = 16 слов
2 2 2 2 A = 16 слов
Итого: 16+16=32 слова
Задача 5
Все пятибуквенные слова, составленные из букв А, Л, Е, Т, Б записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААБ
3. ААААЕ
4. ААААЛ
5. ААААТ
6. АААБА
. . .
Под каким номером в списке идёт первое слово, которое начинается с буквы Л и заканчивается буквой Т?
Решение
Каждому слову поставим в соответствие пятизначное число в пятеричной системе счисления. Для этого каждой букве поставим в соответствие цифру в том порядке, в котором она появляетс в списке.
А — 0, Б — 1, Е — 2, Л — 3, Т — 4
Первое слово, которое начинается на Л — это слово ЛАААА и заканчивающееся на Т — то есть ЛАААТ. Этому слову соответствует число $30004_5$ = $1879_10$, которое стоит под номером 1880.
Задача 6
Все шестибуквенные слова, составленные из букв Б, Л, О, Т записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ББББББ
2. БББББЛ
3. БББББО
4. БББББТ
5. ББББЛБ
6. ББББЛЛ
. . .
Под каким номером стоит слово БОЛОТО?
Решение
Для составления слов используются 4 различных буквы. Поставим в соответствие каждой из букв цифры системы счисления с основанием 4 (с учётом порядка их следования в алфавите): Б — 0, Л — 1, О — 2, Т — 3.
Тогда упорядоченной по алфавиту последовательности слов
1. ББББББ
2. БББББЛ
3. БББББО
4. БББББТ
5. ББББЛБ
6. ББББЛЛ
. . .
будут соответствовать числа в системе счисления с основанием 4:
1. 0000004 = 010
2. 0000014 = 110
3. 0000024 = 210
4. 0000034 = 310
5. 0000104 = 410
5. 0000114 = 510
. . .
Слову БОЛОТО будет соответствовать число 0212324. Переведём это число из системы счисления с основанием 4 в десятичную.
0212324 = 0 · 45 + 2 · 44 + 1 · 43 + 2 · 42 + 3 · 41 + 2 · 40 = 62210.
Заметим, что соответствующая последовательность чисел, записанных в десятичной системе счисления, на 1 меньше номера строки, содержащей данное число. Значит, десятичное число 622 будет находиться на 623-м месте.
Задача 7
Саша составляет 6-значные числа, в которых есть только цифры 1, 2, 3 и 4 причём цифра 1 используется в каждом числе ровно 1 раз. Каждое из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
Пусть цифра 1 стоит в числе на первом месте. Тогда на оставшихся 5 местах может стоять одна из оставшихся цифр 2, 3 или 4. Причём каждая из этих цифр может встречаться в числе любое количество раз. Таким образом нам нужно определить количество 5-значных чисел, состоящих из трёх цифр.
Если M — количество символов в некотором алфавите (мощность алфавита), K — количество всех возможных «слов» (символьных цепочек) длиной N , то = MN.
Следовательно, количество пятизначных чисел, состоящих из трёх цифр, равно 35 = 243. А значит такое же количество 6-значных чисел, в которых на первом месте стоит цифра 1, а на остальных местах цифры 2, 3 или 4, возможно с повтором.
Рассуждая аналогичным образом, мы получим, что такое же количество чисел в 6-значных числах, в которых цифра 1 на втором, третьем, четвёртом, пятом и шестом местах.
То есть всего искомых чисел 6 · 243 = 1458.
Задача 8
Саша составляет четырёхбуквенные слова, в которых есть только буквы Е, Д, О, Н и К, причём в каждом слове буква О используется ровно 2 раза. Каждое из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 9
Саша составляет трёхбуквенные слова, в которых есть только буквы E, C, B, Н, К и У, причём в каждом слове буква К используется ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 10
Все шестибуквенные слова, составленные из букв М, Н, О, П, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ММММММ
2. МММММН
3. МММММО
4. МММММП
5. МММММР
6. ММММНМ
. . .
Укажите слово, которое стоит под номером 267.
Решение
Задача 11
Все пятибуквенные слова, составленные из букв А, М, Н, Т, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААМ
3. ААААН
4. ААААТ
5. ААААУ
6. АААМА
. . .
Под каким номером стоит слово ТУМАН?