Bài 3

Với đa thức hệ số nguyên

P(x)=a_0+a_1x+\cdots+a_kx^k

, gọi

w(P)

là số hệ số lẻ. Đặt

Q_i(x)=(1+x)^i

với

i=0,1,2,\ldots

. Chứng minh rằng nếu

0\le i_1<i_2<\cdots<i_n

thì

w(Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n})\ge w(Q_{i_1})

Bước 1 trên 4: Khối lũy thừa hai chỉ có hai hệ số lẻ

Bước trước Bước tiếp

Hiểu nôm na

Số mũ là lũy thừa của hai làm mẫu nhị thức tách thành một bản thấp và một bản dịch lên cao, không thể triệt tiêu tính lẻ giữa hai bản.

(1+x)^m\equiv1+x^m\pmod 2\quad(m=2^r)

Phân tích chi tiết

Nếu $m=2^r$ , mọi hệ số nhị thức ở giữa $\binom mr$ đều chẵn. Tương đương, lặp lại $(1+x)^{2t}\equiv(1+x^2)^t\pmod2$ cho $(1+x)^m\equiv1+x^m\pmod2$ . Vì vậy, khi nhân với đa thức bậc nhỏ hơn $m$ , hai bản sao nằm ở hai khoảng bậc rời nhau và $w((1+x)^mA)=2w(A)$ .