В 16‐битном регистре процессора 80286 каждый из 16 битов может принимать значения 0 и 1. Таким образом, число, записанное в регистр, представляет собой последовательность из 16 нулей и единиц.
а) Можно ли записать в регистр 30 различных чисел так, чтобы между любыми двумя единицами в записи числа было не менее 7 нулей?
б) Можно ли записать 30 чисел с тем же условием, что и в пункте а), если 5 младших битов регистра (то есть последних цифр в последовательности) неисправны и всегда равны нулю?
в) Сколько различных чисел с не менее чем 7 нулями между любыми двумя единицами можно записать в 16‐битный регистр (со всеми 16 битами)?
Заметим, что если между любыми двумя единицами в записи числа не менее 7 нулей, то в записи числа не может быть более двух единиц. В противном случае понадобится не менее 17 битов (1 + 7 + 1 + 7 + 1) для записи числа.
Без использования единиц можно записать только одно число. С использованием одной единицы — 16 чисел:
0000000000000001, 0000000000000010, 0000000000000100, ... 1000000000000000.
Рассмотрим случай с использованием двух единиц.
Есть 8 чисел, где между единицами ровно 7 нулей:
0000000100000001, 0000001000000010, 0000010000000100, ... 1000000010000000.
Если между единицами ровно 8 нулей, то чисел 7.
Если между единицами ровно 9 нулей, то чисел 6.
Если между единицами ровно 10 нулей, то чисел 5.
...
Наконец, есть только одно число, где между единицами записано 14 нулей.
Итак, при использовании двух единиц получаем 
чисел. (Читатель, знакомый с комбинаторикой, мог бы предпочесть прямому подсчету использование формулы для сочетаний с повторениями 
— количество способов распределить n одинаковых предметов между k ящиками. В нашем случае нужно распределить семь нулей между тремя местами ... 1 ... 00000001 ... . Получаем 
)
Всего можно получить 
числа. Теперь ответим на вопросы задания: а) да, можно записать 30 чисел; в) можно записать 53 различных числа.
Осталось рассмотреть вопрос б). Без использования единиц можно записать только одно число. С использованием одной единицы — 
чисел. С использованием двух единиц, аналогично предыдущему, прямым подсчетом находим 6 возможностей (или: распределяем два нуля между тремя местами ... 1 ... 0000000100000 ... , получаем 
чисел. Всего можно получить 
чисел. Таким образом, ответ на пункт б) таков: нет, нельзя записать 30 чисел.
Ответ: а) да; б) нет; в) 53.
Приведём другое решение.
а) Да. Назовем началом числа первые 5 разрядов, а концом — последние 4. Есть 20 чисел, в которых одна единица стоит в начале и одна в конце (они разделены минимум семью разрядами) и 16 чисел, в которых всего одна единица, это уже 36 чисел.
б) Нет. Имеется всего 11 разрядов для записи. Поскольку в первых пяти и последних 6 разрядах может быть не более одной единицы, всего их не более двух. Разберем случаи:
− если в числе нет единиц, то такое число одно;
− если одна единица, то таких чисел 11;
− если две единицы, то таких чисел 6: три числа, где единица на первом месте, а другая — с 9 по 11 место, два числа, где единица на втором месте и одно число, где единица на третьем месте.
Значит, всего этих чисел 1 + 11 + 6 = 18 < 30.
в) Разбивая число на группы по 8 цифр, получаем, что в каждой группе не более одной единицы, поэтому всего их не более двух. Снова разберем случаи:
− если в числе нет единиц, то такое число одно;
− если одна единица, то таких чисел 16;
− если две единицы, то таких чисел 28: 8, где единица на первом месте, а другая — с 9 по 16 место; ещё 7, где единица на втором месте; ещё 6, в которых единица на третьем месте, и т. д.: 8 + 7 + 6 + ... + 1= 36.
Значит, всего этих чисел 1 + 16 + 36 = 53.