|
|
 |
Условие
Для каждого целого неотрицательного числа i определим число M(i) следующим образом: запишем число i в двоичной форме; если число единиц в этой записи чётно, то M(i) = 0, а если нечётно – то 1 (первые члены этой последовательности: 0, 1, 1, 0, 1, 0, 0, 1, ... ).
а) Рассмотрим конечную последовательность M(0), M(1), ... , M(1000). Докажите, что число членов этой последовательности, равных своему правому соседу, не меньше 320.
б) Рассмотрим конечную последовательность M(0), M(1), ..., M(1000000). Докажите, что число таких членов последовательности, что M(i) = M(i + 7), не меньше 450000.
Решение
а) Все двоичные числа, оканчивающиеся на 01, удовлетворяют условию M(i) = M(i + 1). Среди четырёх последовательных чисел ровно одно оканчивается на 01, поэтому таких чисел 250. Кроме этого, нам подходят числа, оканчивающиеся на 0111 (их не меньше чем 248 : 4 = 62) и оканчивающиеся на 011111 (их не меньше чем 60 : 4 = 15). Всего 250 + 62 + 15 = 325 > 320.
б) Легко проверить, что условию M(i) = M(i + 7), удовлетворяют двоичные числа, оканчивающиеся на 0001, 0011, 0100, 0101 и 0111. Так как
i ≤ 999993, то таких чисел не меньше чем 5·[999994 : 16] = 312495. Кроме того, нас устраивают числа, оканчивающиеся на 01010 и 01110 (их не менее
2·[999994 : 32] = 62498) и оканчивающиеся на 011001, 011011, 011100, 011101 и 011111 (их не менее 5·[999994 : 64] = 78120). Всего
312495 + 62498 + 78120 = 453113 > 450000.
Замечания
Можно найти и точное количество указанных членов последовательности.
а) Нетрудно проверить, что искомые числа – это в точности те, двоичная запись которых оканчивается на нечётное число нулей. То есть это числа, в разложение которых двойка входит в нечётной степени. Найдём их количество.
Чётных чисел, не превосходящих n, ровно [n/2]. Из них надо вычесть количество [n/4] чисел, кратных 4. Но при этом мы вычли и числа, кратные 8. Чтобы их учесть добавим [n/8]. Теперь, нужно вычесть [n/16] (количество чисел, кратных 16); и т. д. Итак,
Kn = [n/2] – [n/4] + [n/8] – [n/16] + ...
В частности, K1000 = 500 – 250 + 125 – 62 + 31 – 15 + 7 – 3 + 1 = 334.
б) Число k = 106 не удовлетворяет условию (двоичная запись 106 кончается на 6 нулей, а двоичная запись числа 1000007 получается из нее заменой трёх последних нулей на единицы). Далее везде считаем k < 106.
Пусть M(k) = M(k + 7). Возможны два случая.
1) M(k) = M(k + 8), M(k + 7) = M(k + 8).
По каждому числу k ≥ 8 построим число k = [k/8]; двоичная запись k получается из двоичной записи k отбрасыванием трёх последних цифр. Равенство
M(k) = M(k + 8) эквивалентно равенству M(k) = M(k + 1). Это согласно п. а) означает, что двоичная запись числа k + 1 = k + 8 оканчивается нечётным числом нулей. Количество таких чисел равно K125000 = 41667 (что нетрудно вычислить по вышеприведенной формуле).
Чтобы одновременно выполнялось равенство M(k + 7) = M(k + 8), двоичная запись числа k + 8 должна оканчиваться на нечётное число нулей. Это может быть только один нуль (три нуля состыкуются с нечётным числом нулей на конце k + 8 и дадут уже чётное число нулей). Итак, к каждой из K125000 хороших записей k + 8 можно приписать 010 или 110, что дает 2K125000 чисел.
2) M(k) ≠ M(k + 8), M(k + 7) ≠ M(k + 8).
Первое неравенство можно записать в виде M(k) ≠ M(k + 1). Это означает, что двоичная запись числа k + 1 = k + 8 оканчивается чётным числом нулей. Количество таких чисел равно 125000 – K125000.
Неравенство M(k + 7) ≠ M(k + 8) означает, что двоичная запись числа k + 8 должна оканчиваться на чётное число нулей.
Это могут быть два нуля (то есть три последние цифры 100) или ни одного (последние три цифры **1). Всего 5 вариантов. Итак, в этом случае имеем
5(125000 – K125000) чисел.
С учетом первого случая получаем 725000 – 3K125000 = 499999 чисел, удовлетворяющих условию.
2. Баллы: 2 + 5.
