前些天352问的一道集合题

kuing

2013-11-19
三下五除二 13:53:41

第四个，一个学生老问我，方便的话解答一下，或者发你论坛
kuing 14:05:05
有点难的竞赛题
晚点再想
吃饭
三下五除二 15:25:55
ok
kuing 15:26:47
答案大概想到了，不过严格论证还没想好
三下五除二 15:29:22
对竞赛这种还是不行，脑子里乱，我觉得应该考虑有几个数构成等差数列有关吧
kuing 15:56:47
论证太难了，想倒是能想到……
三下五除二 16:20:19
你要是认为难拿就是真难了，
kuing 16:21:19
想倒不是很难，只是我不太懂得怎么样去用数学语言去论证
PS、我很少玩这类题，我认为难也不一定真难……

题目：设 $a_1$, $a_2$, $\ldots$, $a_{20}$ 是 20 个两两不同的整数，且集合 $\{a_i+a_j\mid1\leqslant i\leqslant j\leqslant20\}$ 中有 201 个不同的元素，求集合 $\bigl\{\abs{a_i-a_j}\bigm|1\leqslant i<j\leqslant20\bigr\}$ 中不同元素个数的最小可能值。

如聊天记录所说，这道题是前些天352问我的，当时我虽然很快就想到了答案，但是更多只是凭着直觉得到结论，还没有严格的数学论证，然而该怎么论证却让我想了好久也想不出来，后来督波去了，就放到一边没想了，直到昨晚睡不着，又想起此题，躺着仔细想才把过程理得比较清晰，不过现在写起来在表达上仍然不太容易。

为方便叙述，先作一些约定。

对于有 $n$ 个数的数组 $X=(x_1, x_2, \ldots, x_n)$，如果集合 $\{x_i\mid 1\leqslant i\leqslant n\}$ 有 $n-m$ 个元素，则称 $X$ 有 $m$ 个重复。
$X$ 中每两个数之间的关系要么是“$=$”要么是“$\ne$”，如果“$=$”的个数共 $M$ 个，则称 $X$ 有 $M$ 个等号。

例如数组 $(1,2,2,3,3,3,4,4,4,4,5)$ 有 6 个重数，有 10 个等号。

不难证明，如果某数组有 $m$（$m\geqslant 1$）个重复，$M$ 个等号，则必有 $m\leqslant M\leqslant C_{m+1}^2$。
（这个结论也是那种看着显然，但是不太好写证明的，有空再补一下吧）

回到原题。

记由 $a_i+a_j$, $1\leqslant i\leqslant j\leqslant20$ 所构成的数组为 $A$，因为 $i$ 和 $j$ 可以相等，所以 $A$ 有 $C_{20}^2+20=210$ 个数，而集合 $\{a_i+a_j\mid1\leqslant i\leqslant j\leqslant20\}$ 只有 201 个的元素，即 $A$ 有 9 个重复，设 $A$ 有 $M_1$ 个等号，则由上述结论有
\[9\leqslant M_1\leqslant C_{10}^2. \quad(1)\]

记由 $\abs{a_i-a_j}$, $1\leqslant i<j\leqslant20$ 所构成的数组为 $B$，这里 $i$ 和 $j$ 不能等了，所以 $B$ 有 $C_{20}^2=190$ 个数，设 $B$ 有 $m_2$ 个重复，则集合 $\bigl\{\abs{a_i-a_j}\bigm|1\leqslant i<j\leqslant20\bigr\}$ 的元素个数为 $190-m_2$，于是问题就是要求 $m_2$ 的最大值。设 $B$ 有 $M_2$ 个等号，则
\[m_2\leqslant M_2\leqslant C_{m_2+1}^2. \quad(2)\]

由于各 $a_i$ 不相等，因此，$A$ 中的等号只能是像 $a_1+a_2=a_3+a_4$ 或者 $a_1+a_2=2a_3$ 这样的两类等式，$B$ 中的则是 $\abs{a_1-a_2}=\abs{a_3-a_4}$ 或者 $\abs{a_1-a_2}=\abs{a_2-a_3}$。

因为
\begin{align*}
a_1+a_2=a_3+a_4 &\riff \abs{a_1-a_3}=\abs{a_2-a_4}~\text{且}~\abs{a_1-a_4}=\abs{a_2-a_3},\\
a_1+a_2=2a_3 &\riff \abs{a_1-a_3}=\abs{a_2-a_3},
\end{align*}
而且
\begin{align*}
\abs{a_1-a_2}=\abs{a_3-a_4} &\riff a_1+a_3=a_2+a_4~\text{异或}~a_1+a_4=a_2+a_3,\\
\abs{a_1-a_2}=\abs{a_2-a_3} &\riff a_1+a_3=2a_2,
\end{align*}
（“异或”是指两个中有且只一个成立）
可见 $A$ 中的每一个等号对应着 $B$ 中的一个或两个等号，而 $B$ 中的每一个等号对应着 $A$ 中的一个等号，所以
\[M_1\leqslant M_2\leqslant 2M_1. \quad(3)\]

由 (1), (2), (3) 我们得到
\[m_2\leqslant M_2\leqslant 2M_1\leqslant 2C_{10}^2=90,\]
所以集合 $\bigl\{\abs{a_i-a_j}\bigm|1\leqslant i<j\leqslant20\bigr\}$ 的元素个数 $190-m_2\geqslant 100$。

最后再举一个例子说明可以取 100，比如
\[(a_1, a_2, \ldots, a_{20})=(1^4, 2^4, 3^4, \ldots, 10^4, -1^4, -2^4, -3^4, \ldots, -10^4),\]
已用软件验证。


PS、题目的叙述中后面的“不同元素”中的“不同”二字是多余的，因为既然是集合了，元素当然是不同的。

kuing

话说其他的几题除了第3题是熟悉的经典老问题之外都不太简单的样子……

其妙

，牛笔！

kuing

现在至少还差两样东西有待做好：
1、$m\leqslant M\leqslant C_{m+1}^2$ 的具体证明；
2、上面最后构造的例子难以手工验证，能否构造一个无需借用程序只要用推理就能直接验证的例子？

kuing

1# 最后的例子用 Mathematica7 验证如下：

1. Table[a[i] = i^4, {i, 1, 10}];
2. Table[a[i] = -a[i - 10], {i, 11, 20}];
3. Table[a[i], {i, 1, 20}]
4. A = Flatten[Table[a[i] + a[j], {i, 1, 20}, {j, i, 20}]];
5. Length[A]
6. Length[Union[A]]
7. B = Flatten[Table[Abs[a[i] - a[j]], {i, 1, 19}, {j, i + 1, 20}]];
8. Length[B]
9. Length[Union[B]]

Copy the Code

输出
{1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, -1, -16, -81, -256, -625, -1296, -2401, -4096, -6561, -10000}
210
201
190
100

后面的四个数分别就是1#证明过程提到的数值，这说明那列数是符合的。