MathLabs

第4题

证明对每个正整数 tt，都存在唯一的 0,1,…,t−10,1,\ldots,t-1 的排列 a0,a1,…,at−1a_0,a_1,\ldots,a_{t-1}，使得对每个 0≤i≤t−10\le i\le t-1，二项式系数 (t+i2ai)\binom{t+i}{2a_i} 为奇数且 2ai≠t+i2a_i\neq t+i。
第 1/6 步：通过位位置集合表述库默尔定理
上一步下一步
(t+i2ai) odd  ⟺  S(2ai)⊆S(t+i)\binom{t+i}{2a_i}\text{ odd}\iff S(2a_i)\subseteq S(t+i)
详细分析

对非负整数 xx，设 S(x)S(x) 为 xx 的二进制展开中数字 11 所在位置的集合。库默尔定理指出，(nk)\binom{n}{k} 为奇数恰好当 kk 与 n−kn-k 用二进制相加不产生进位时，等价于 S(k)⊆S(n)S(k)\subseteq S(n)。由于 2ai<t+i2a_i<t+i，条件 2ai≠t+i2a_i\neq t+i 与 (t+i2ai)\binom{t+i}{2a_i} 为奇数结合起来，意味着 S(2ai)S(2a_i) 是 S(t+i)S(t+i) 的真子集。