Задача 60909

Темы:    [ Системы счисления (прочее) ] [ Индукция (прочее) ]

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

Условие

Докажите, что каждое целое число A представимо в виде

A = a₀ + 2a₁ + 2²a₂ +...+ 2ⁿa_n,

где каждое из чисел a_k = 0, 1 или -1 и a_ka_{k + 1} = 0 для всех 0 k n - 1, причем такое представление единственно.

Решение

Если A четно, то представление числа A получается из представления меньшего числа m = A/2 `` сдвигом'' на один разряд. Если же A нечетно, то a<sub>0</sub> = ±1 и число a<sub>1</sub> должно равняться нулю; поэтому число A - a<sub>0</sub> делится на 4 и представление числа A получается из представления меньшего числа m = (A - a<sub>0</sub>)/4 ``сдвигом'' на два разряда и добавлением цифры a₀. В обоих случаях единственность представления числа A следует из единственности представления числа m.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	3
Название	Двоичная и троичная системы счисления
Тема	Двоичная система счисления
задача
Номер	05.071