Задача 60417

Темы:    [ Треугольник Паскаля и бином Ньютона ] [ Системы счисления (прочее) ]

Сложность: 3+ Классы: 9,10 Название задачи: Биномиальная система счисления.

Условие

Покажите, что любое натуральное число n может быть представлено в виде     где x, y, z – такие целые числа, что  0 ≤ x < y < z,  либо  0 = x = y < z.

Решение

Пусть z – наибольшее число, для которого      Тогда "остаток"     Если  r > 0,  пусть y – наибольшее число, для которого     При этом число     можно записать в виде      где  x < y.
С другой стороны, наибольшее число, которое можно представить в таком виде с использованием     это

  

поэтому представить наше число n другим способом не удастся.

Замечания

Аналогично можно доказать, что любое натуральное число n может быть единственным образом представлено в виде     с соответствующими ограничениями на числа x₁, ..., x_k.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	3
Название	Размещения, перестановки и сочетания
Тема	Классическая комбинаторика
задача
Номер	02.083