Олимпиадная задача Канель-Беловой по последовательности единиц в системах счисления
Задача
Для каждого целого неотрицательного числа 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.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь