Задача 32881

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

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

Условие

Автор: Фольклор

Найти количество нечётных чисел в n-й строке треугольника Паскаля.

Решение

Рассмотрим над полем Z₂ из двух элементов многочлен  (1 + x)ⁿ.  Нас интересует число его отличных от нуля коэффициентов (назовём это число весом многочлена). Действительно, коэффициент при x^k равен 1, если    нечётно, и нулю в противном случае. Заметим, теперь, что над нашим полем
(1 + x)² = 1 + x²,  (1 + x)⁴ = (1 + x²)² = 1 + x⁴,  ...,   (1 + x)^2m = 1 + x^2m.  Кроме того, если f(x) – многочлен степени, меньшей m, то вес многочлена  f(x)(1 + x^m)  в два раза больше веса  f(x) (при раскрытии скобок не появляется подобных членов). Отсюда ясно, что если
n = 2^m₁ + 2^m₂ + ... + 2^m_k  (m₁ < m₂ < ... < m_k)  – двоичное разложение числа n, то вес многочлена   (1 + x)ⁿ = (1 + x)^2m₁(1 + x)^2m₂... = (1 + x^2m₁)(1 + x^2m₂)...  равен 2^k.

Ответ

2^k, где k – количество единиц в двоичном разложении числа n.