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。
第 6/6 步：归纳法构造出唯一的配对
上一步下一步
∃! pairing of small and big numbers  ⟹  ∃! (a0,…,at−1)\exists!\text{ pairing of small and big numbers}\implies\exists!\ (a_0,\ldots,a_{t-1})
详细分析

对 tt 归纳可证：小数 {0,…,⌈t/2⌉−1}\{0,\ldots,\lceil t/2\rceil-1\} 可以与大数 {⌈t/2⌉,…,t−1}\{\lceil t/2\rceil,\ldots,t-1\} 唯一配对，使每个小数 xx 与其配对的大数 yy 满足 S(x)⊊S(y)S(x)\subsetneq S(y)，∣S(x)∣=∣S(y)∣−1|S(x)|=|S(y)|-1：去掉大数范围中形如 2a2^a 的唯一的幂，强迫 2a2^a 与 2a−2a=02^a-2^a=0 配对；剩下的数分成两个更小的配对问题，由双射 z↦2a−1−zz\mapsto 2^a-1-z 连接，由归纳假设知这是唯一的。结合 t+it+i 为奇数时的直接公式，即得问题所要求的唯一排列 a0,…,at−1a_0,\ldots,a_{t-1}。