Задача
Пустьaиb— целые числа. Напишем числоbсправа от числаa. Если числоaчётное, то разделим его на 2, если оно нечётное, то сначала вычтем из него единицу, а потом разделим его на 2. Получившееся числоa1напишем под числомa. Справа от числаa1напишем число 2b. С числомa1проделаем ту же операцию, что и с числомa, и, получив числоa2, напишем его под числомa1. Справа от числаa2напишем число 4bи так далее. Этот процесс продолжаем до тех пор, пока не получим в левом столбце число 1. Доказать, что сумма тех чисел правого столбца, слева от которых стоят нечётные числа, равна произведениюab.
Решение
Рассмотрим двоичную запись числаa=$\overline{\alpha_n\dots\alpha_0}$. Пустьi1,...,is — позиции, на которых стоят 1, тогдаa=$\sum^{n}{i=0}$$\alpha{i}^{}$2i=$\sum^{s}{t=1}$$\alpha{i_t}^{}$2it=$\sum^{s}{t=1}$2it. Заметим, чтоaiнечётно тогда и только тогда, когда наi-ой позиции двоичной записи числаaстоит 1. Поскольку справа отaiстоитb . 2i, а значит, искомая сумма равна$\sum^{s}{t=1}$b2it=b$\sum^{s}_{t=1}$2it=ab.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь