Задание 10. Системы счисления и комбинаторика. ЕГЭ 2020 по информатике
Средний процент выполнения: 57.8%
Ответом к заданию 10 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Все шестибуквенные слова, составленные из букв Б, Л, О, Т записаны в алфавитном порядке и пронумерованы. Вот начало списка:
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-м месте.
Задача 2
Саша составляет 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.
Задача 3
Саша составляет шестибуквенные слова, в которых есть только буквы А, М, О, К, Т и С, причём в каждом слове буква Т используется один или два раза и при этом может стоять только на первом или на втором местах, а буква О встречается в слове ровно 2 раза, на пятом и шестом месте. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 4
Саша составляет шестизначные числа, в которых есть только цифры 1, 2 и 3, причём цифра 1 используется в каждом числе не более двух раз и при этом может стоять только на первом или втором местах. Каждая из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
Задача 5
Саша составляет пятизначные числа, в которых есть только цифры 1, 2, 3 и 4, причём цифра 1 используется в каждом числе не более двух раз, и при этом может стоять только на первом или на последнем месте. Каждая из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
Задача 6
Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква Г используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 7
Саша составляет четырёхбуквенные слова, в которых есть только буквы Е, Д, О, Н и К, причём в каждом слове буква О используется ровно 2 раза. Каждое из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 8
Саша составляет трёхбуквенные слова, в которых есть только буквы E, C, B, Н, К и У, причём в каждом слове буква К используется ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 9
Все шестибуквенные слова, составленные из букв М, Н, О, П, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ММММММ
2. МММММН
3. МММММО
4. МММММП
5. МММММР
6. ММММНМ
. . .
Укажите слово, которое стоит под номером 267.
Решение
Задача 10
Аня составляет 5-буквенные слова, в которых встречаются только буквы А, Б, В. Причем буква A может встречаться только первой или последней (двух букв А в слове быть не может), но при этом должна присутствовать обязательно. Каждая из других допустимых букв может встречаться в слове на любом месте или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Аня?
Решение
Задача 11
Все пятибуквенные слова, составленные из букв А, М, Н, Т, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААМ
3. ААААН
4. ААААТ
5. ААААУ
6. АААМА
. . .
Под каким номером стоит слово ТУМАН?
Решение
Задача 12
Все пятибуквенные слова, составленные из букв А, Б, Е, Л, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААБ
3. ААААЕ
4. ААААЛ
5. ААААТ
6. АААБА
. . .
Под каким номером в списке идёт первое слово, которое начинается с буквы Б и заканчивается буквой Е?