MathLabs

第5题

设 nn 为正整数。一对整数分量的 nn 元组 (a1,…,an)(a_1,\ldots,a_n) 与 (b1,…,bn)(b_1,\ldots,b_n) 称为「exquisite」的，如果 ∣a1b1+⋯+anbn∣≤1|a_1b_1+\cdots+a_nb_n|\le1。求整数分量的互不相同的 nn 元组的最大个数，使得其中任意两个都构成一个 exquisite 对。
第 5/5 步：用引理反证限界 ∣Ai∣|A_i|
上一步下一步
∣Ai∣≥2i+1  ⟹  ∃ a,b∈Ai: a1b1+⋯+aibi≥2  ⟹  contradiction|A_i|\ge2i+1 \implies \exists\, a,b\in A_i:\ a_1b_1+\cdots+a_ib_i\ge2 \implies \text{contradiction}
详细分析

假设 ∣Ai∣≥2i+1|A_i|\ge2i+1。AiA_i 中唯一非零分量位于位置 ii 的元组至多有两个（三个的话必有两个同号，导致 ∣aibi∣≥2|a_ib_i|\ge2，违反 exquisite 性）；将它们去掉，并对第 ii 个坐标为负的剩余元组取反（这保持 exquisite 性）。在剩下至少 2i−22i-2 个元组中，或者有两个的前 i−1i-1 个坐标相同（此时 a1b1+⋯+ai−1bi−1≥1a_1b_1+\cdots+a_{i-1}b_{i-1}\ge1），或者对它们截断得到的 (i−1)(i-1) 元组应用引理，得到两个满足 a1b1+⋯+ai−1bi−1≥1a_1b_1+\cdots+a_{i-1}b_{i-1}\ge1 的元组。无论哪种情况，加上第 ii 个坐标的正贡献 aibi≥1a_ib_i\ge1，内积总和至少为 22，与 exquisite 假设矛盾。因此 ∣Ai∣≤2i|A_i|\le2i，对 ii 求和得 ∣A∣≤n2+n|A|\le n^2+n，故两两 exquisite 的元组最大个数为 1+n2+n=n2+n+11+n^2+n=n^2+n+1，与构造相符。