免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 前些天352问的一道集合题

2013-11-19
三下五除二 13:53:41
QQ图片20131207140512.jpg
2013-12-7 14:08

第四个,一个学生老问我,方便的话解答一下,或者发你论坛
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、题目的叙述中后面的“不同元素”中的“不同”二字是多余的,因为既然是集合了,元素当然是不同的。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

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

TOP

,牛笔!

TOP

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

TOP

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]]
复制代码
输出
{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#证明过程提到的数值,这说明那列数是符合的。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

返回列表 回复 发帖