Задача 60914

Тема:    [ Ним-сумма ]

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

Условие

Ним-сумма. Будем говорить, что число n является ним-суммой чисел m и k ( m k = n), если оно получается из чисел m и k после следующих преобразований.
1) m и k записываются в двоичной системе счисления

m = (m_s...m₁m₀)₂,        k = (k_s...k₁k₀)₂

(меньшее число дополняется спереди нулями).
2) Полученные наборы цифр как векторы складываются покомпонентно по модулю 2:

(m_s,..., m₁, m₀) + (k_s,..., k₁, k₀) (n_s,..., n₁, n₀)(mod 2).

3) Набор цифр (n_s,..., n₁, n₀) переводится в число n:

(n_s...n₁n₀)₂ = n.

Например, 4 7 = 3, так как

4 = (100)₂,    7 = (111)₂,    (1, 0, 0) + (1, 1, 1) (0, 1, 1)(mod 2),    (011)₂ = 3.

Докажите, что ним-сумма удовлетворяет следующим свойствам:
а) m m = 0; б) m k = k m; в) (m t) k = m (t k);
г) если n 0 и

m1 m2 ... ml = n,

(5.1)

то найдется такой номер j ( 1 j l), для которого m_j n < m_j.

Решение

г) Пусть n = (n_s...n₁n₀)₂, где n_s = 1. Тогда у одного из чисел m₁, m₂, ..., m_l в s-ом разряде также стоит единица. Если m_j — одно из таких чисел, то m_j n < m_j.

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

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