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。
第 3/6 步：鸽笼原理迫使亏量恰为一位
上一步下一步
∣S(t+i)∣−∣S(2ai)∣=1for every i=0,…,t−1|S(t+i)|-|S(2a_i)|=1\quad\text{for every }i=0,\ldots,t-1
详细分析

由于 a0,…,at−1a_0,\ldots,a_{t-1} 是 0,…,t−10,\ldots,t-1 的一个排列，多重集 {S(2ai)}i=0t−1\{S(2a_i)\}_{i=0}^{t-1} 等于 {S(2i)}i=0t−1\{S(2i)\}_{i=0}^{t-1}，故 ∑i∣S(2ai)∣=∑i∣S(2i)∣\sum_i|S(2a_i)|=\sum_i|S(2i)|。结合前面的恒等式得 ∑i(∣S(t+i)∣−∣S(2ai)∣)=t\sum_i\big(|S(t+i)|-|S(2a_i)|\big)=t。由第一步，这 tt 项每项都至少为 11，所以每项恰好等于 11：∣S(t+i)∣−∣S(2ai)∣=1|S(t+i)|-|S(2a_i)|=1 对每个 ii 成立。