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。
第 2/6 步：位数恒等式
上一步下一步
∑i=0t−1∣S(t+i)∣=t+∑i=0t−1∣S(2i)∣\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)|
详细分析

因为 S(2i)={1+x:x∈S(i)}S(2i)=\{1+x:x\in S(i)\} 且 S(2i+1)={0}∪{1+x:x∈S(i)}S(2i+1)=\{0\}\cup\{1+x:x\in S(i)\}（附加一个二进制数字），对 tt 作简短归纳即得 ∑i=0t−1∣S(t+i)∣=t+∑i=0t−1∣S(2i)∣\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)|：每一步都把 tt 个连续整数上的和拆成较小的 tt 个整数上的和，再加上每对 (2i,2i+1)(2i,2i+1) 多出的一个置位。