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。
第 4/6 步：奇数下标被直接确定
上一步下一步
t+i odd  ⟹  ai=t+i−12t+i\text{ odd}\implies a_i=\frac{t+i-1}{2}
详细分析

若 t+it+i 为奇数，则 t+it+i 的第 00 位为 11，而 2ai2a_i 的第 00 位恒为 00。由第三步，S(t+i)S(t+i) 中恰有一位不在 S(2ai)S(2a_i) 中，该缺失位必为第 00 位，故 S(2ai)=S(t+i)∖{0}S(2a_i)=S(t+i)\setminus\{0\}，即 2ai=t+i−12a_i=t+i-1，ai=(t+i−1)/2a_i=(t+i-1)/2。这对每个使 t+it+i 为奇数的 ii 唯一确定了 aia_i。