РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 5357 Добавить в вариант

Выведите признак делимости на три чисел, записанных в двоичной системе.

Решение.

Задача очень проста для тех, кто знаком с «теорией сравнений»: так как $2\equiv минус 1 левая круглая скобка mod 3 правая круглая скобка ,$ то $2 в степени k \equiv левая круглая скобка минус 1 правая круглая скобка в степени k левая круглая скобка mod 3 правая круглая скобка ,$ значит,

$a_n a_n минус 1\ldots a_0=a_n 2 в степени n плюс a_n минус 12 в степени левая круглая скобка n минус 1 правая круглая скобка плюс \ldots=a_0 минус a_1 плюс \ldots плюс левая круглая скобка минус 1 правая круглая скобка в степени n левая круглая скобка mod3 правая круглая скобка ,$

откуда и следует результат. Или же можно просто доказать, что $2 в степени k минус левая круглая скобка минус 1 правая круглая скобка в степени k \vdots 3.$

Ответ: разность между числом единиц, стоящих на четных местах в данном числе, и числом единиц, стоящих на нечетных местах, делится на 3.

Классификатор: Алгебра: числа. Различные системы счисления

Спрятать решение · Помощь