MathLabs

Bài 4

Chứng minh rằng với mọi số nguyên dương tt, tồn tại duy nhất một hoán vị a0,a1,…,at−1a_0,a_1,\ldots,a_{t-1} của 0,1,…,t−10,1,\ldots,t-1 sao cho, với mọi 0≤i≤t−10\le i\le t-1, hệ số nhị thức (t+i2ai)\binom{t+i}{2a_i} là số lẻ và 2ai≠t+i2a_i\neq t+i.
Bước 1 trên 6: Định lý Kummer qua tập vị trí bit
Bước trướcBước tiếp
(t+i2ai) odd  ⟺  S(2ai)⊆S(t+i)\binom{t+i}{2a_i}\text{ odd}\iff S(2a_i)\subseteq S(t+i)
Phân tích chi tiết

Với số nguyên không âm xx, gọi S(x)S(x) là tập các vị trí có chữ số 11 trong khai triển nhị phân của xx. Định lý Kummer nói rằng (nk)\binom{n}{k} là số lẻ đúng khi cộng kk và n−kn-k trong hệ nhị phân không sinh ra số nhớ, tương đương S(k)⊆S(n)S(k)\subseteq S(n). Vì 2ai<t+i2a_i<t+i, điều kiện 2ai≠t+i2a_i\neq t+i cùng với (t+i2ai)\binom{t+i}{2a_i} lẻ nghĩa là S(2ai)S(2a_i) là tập con thực sự của S(t+i)S(t+i).