Задание 10. Системы счисления и комбинаторика. ЕГЭ 2020 по информатике
Средний процент выполнения: 57.8%
Ответом к заданию 10 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
На одном предприятии работает 300 человек. Для каждого работника необходимо завести карточку, номер которой состоял бы из цифр 2, 5, 7. При этом все номера карт должны иметь одну длину и быть различными. Определите минимальную длину номера карты.
Решение
Если M — количество символов в некотором алфавите (мощность алфавита ), K — количество всех возможных «слов» (символьных цепочек) длиной N, то = MN.
В нашем случае для составления номеров используются только 3 цифры, значит M = 3. Карточек должно хватить на 300 работников, значит, K ≥ 300. Согласно условию, нам нужно найти наименьшее N, для которого 3N ≥ 300. Значение N можно искать подбором, последовательно подставляя в выражение числа 1, 2, 3, 4, . . . . В результате получим, что искомое значение N = 6.
Можно также воспользоваться логарифмической функцией N = logMK. Если logMK не является целым числом, то его нужно округлить в большую сторону или найти значение logMK , где K — ближайшая целая степеньM, K > K. Тогда N = log3300 ≈ log3729 = 6.
Задача 2
Все шестибуквенные слова, составленные из букв Б, Л, О, Т записаны в алфавитном порядке и пронумерованы. Вот начало списка:
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-м месте.
Задача 3
Саша составляет 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.
Задача 4
Саша составляет шестибуквенные слова, в которых есть только буквы А, М, О, К, Т и С, причём в каждом слове буква Т используется один или два раза и при этом может стоять только на первом или на втором местах, а буква О встречается в слове ровно 2 раза, на пятом и шестом месте. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 5
Саша составляет четырёхбуквенные слова, в которых есть только буквы А, Б, О, Р, С и Т, причём в каждом слове буква Р используется один или два раза и при этом может стоять только на первом или на последнем месте, а буква О встречается ровно один раз и стоит на втором месте. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Саша?
Решение
Задача 6
Саша составляет шестизначные числа, в которых есть только цифры 1, 2 и 3, причём цифра 1 используется в каждом числе не более двух раз и при этом может стоять только на первом или втором местах. Каждая из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
Задача 7
Саша составляет пятизначные числа, в которых есть только цифры 1, 2, 3 и 4, причём цифра 1 используется в каждом числе не более двух раз, и при этом может стоять только на первом или на последнем месте. Каждая из других допустимых цифр может встречаться в числе любое количество раз или не встречаться совсем. Сколько существует таких чисел, которые может написать Саша?
Решение
Задача 8
Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква Г используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 9
Саша составляет четырёхбуквенные слова, в которых есть только буквы Е, Д, О, Н и К, причём в каждом слове буква О используется ровно 2 раза. Каждое из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 10
Саша составляет трёхбуквенные слова, в которых есть только буквы E, C, B, Н, К и У, причём в каждом слове буква К используется ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Саша?
Решение
Задача 11
Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква А используется ровно 1 раз. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.Сколько существует таких слов, которые может написать Саша?
Решение
Задача 12
Все шестибуквенные слова, составленные из букв А, Б, В, Г, Д, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААААА 4. АААААГ 7. ААААББ
2. АААААБ 5. АААААД 8. ААААБВ
3. АААААВ 6. ААААБА 9. . . .
Укажите слово, которое стоит под номером 357.
Решение
Задача 13
Все шестибуквенные слова, составленные из букв М, Н, О, П, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ММММММ
2. МММММН
3. МММММО
4. МММММП
5. МММММР
6. ММММНМ
. . .
Укажите слово, которое стоит под номером 267.
Решение
Задача 14
Дима составляет 6-буквенные слова, в которых встречаются только буквы А, Б, В. Причём буква A может стоять только на первом, втором или третьем месте и встречаться или ровно один раз, или ровно три раза, или не встречаться вовсе. Каждая из других допустимых букв может встречаться в слове на любом месте или не встречаться совсем. Словом, считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Дима?
Решение
Задача 15
Аня составляет 5-буквенные слова, в которых встречаются только буквы А, Б, В. Причем буква A может встречаться только первой или последней (двух букв А в слове быть не может), но при этом должна присутствовать обязательно. Каждая из других допустимых букв может встречаться в слове на любом месте или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Аня?
Решение
Задача 16
Дима составляет 6-буквенные слова, в которых встречаются только буквы А, Б, В. Причём буква A может встречаться только на первом или втором местах (а также первом и втором местах одновременно или не встречаться вовсе), каждая из других допустимых букв может встречаться в слове на любом месте или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Дима?
Решение
Задача 17
Все пятибуквенные слова, составленные из букв А, М, Н, Т, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААМ
3. ААААН
4. ААААТ
5. ААААУ
6. АААМА
. . .
Под каким номером стоит слово ТУМАН?
Решение
Задача 18
Все шестибуквенные слова, составленные из букв И, М, С, Я, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ИИИИИИ
2. ИИИИИМ
3. ИИИИИС
4. ИИИИИЯ
5. ИИИИМИ
6. ИИИИММ
. . .
Под каким номером стоит слово МИССИЯ?
Решение
Задача 19
Все пятибуквенные слова, составленные из букв А, Б, Е, Л, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААБ
3. ААААЕ
4. ААААЛ
5. ААААТ
6. АААБА
. . .
Под каким номером в списке идёт первое слово, которое начинается с буквы Б и заканчивается буквой Е?
Решение
Задача 20
Всешестибуквенные слова, составленные из букв Б,Л,О, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ББББББ
2. БББББЛ
3. БББББО
4. БББББТ
5. ББББЛБ
6. ББББЛЛ
. . .
Под каким номером в списке идёт первое слово, которое начинается с буквы O?