Задача 78169

Темы:    [ Двоичная система счисления ] [ Процессы и операции ]

Сложность: 2+ Классы: 8,9

Условие

Пусть a и b — целые числа. Напишем число b справа от числа a. Если число a чётное, то разделим его на 2, если оно нечётное, то сначала вычтем из него единицу, а потом разделим его на 2. Получившееся число a₁ напишем под числом a. Справа от числа a₁ напишем число 2b. С числом a₁ проделаем ту же операцию, что и с числом a, и, получив число a₂, напишем его под числом a₁. Справа от числа a₂ напишем число 4b и так далее. Этот процесс продолжаем до тех пор, пока не получим в левом столбце число 1. Доказать, что сумма тех чисел правого столбца, слева от которых стоят нечётные числа, равна произведению ab.

Решение

Рассмотрим двоичную запись числа a = . Пусть i₁,..., i_s — позиции, на которых стоят 1, тогда a = 2ⁱ = 2^i_t = 2^i_t. Заметим, что a_i нечётно тогда и только тогда, когда на i-ой позиции двоичной записи числа a стоит 1. Поскольку справа от a_i стоит b ^. 2ⁱ, а значит, искомая сумма равна b2^i_t = b2^i_t = ab.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	22
Год	1959
вариант
Класс	7
Тур	1
задача
Номер	1