请教集合问题

snowblink

记有限集$M$中的元素个数为$\left | M \right | $，已知实数集合$A = \left \{ a_1, a_2,\cdots ,a_n \right \} $，实数集合$B= \left \{ b_1, b_2,\cdots ,b_n \right \}$，设$P = \left \{ a_i+a_j\mid a_i,a_j\in A,i \neq  j \right \} $，$Q = \left \{ b_ib_j\mid b_i,b_j\in B,i \neq  j \right \} $，求$\left | P \right | $与$\left | Q \right | $的最小值.
答案分别是15和13

Czhang271828

$n=9$ 漏了? 按照以下推导, $2n-3=15$, $2n-5=13$.


第一问. 不妨设 $a_1<a_2<\cdots <a_n$, 那么
$$
a_1+a_2< a_1+a_3<\cdots <a_1+a_n<a_2+a_n<\cdots <a_{n-1}+a_n.
$$
以上出现了 $2n-3$ 个不同的数, 从而最小值不小于 $2n-3$. 等差数列可以取等.

第二问: 不妨假设 $0\in B$, 理由如下:

• 若 $|Q|$ 取最小值时 $0\notin B$, 则可以把 $B$ 中模长最大的数 (之一) 换做 $0$, 使得 $|Q|$ 的值不增加.
  

不妨设 $|b_1|\geq |b_2|\geq \cdots \geq |b_{n-1}|>|b_n|=0$, 我们断言
$$
b_1b_2,b_1b_3,\cdots b_{1,n-2},b_1b_{n-1},b_2b_{n-1},\cdots , b_{n-2}b_{n-1}
$$
中至多重复一个数. 记上述数列为 $c_i$, 可以发现:

• $c_i\neq c_{i+1}$ 恒成立, 给相邻两项消去相同的 $b_l$ 即可;
• $|b_k|>|b_{k+2}|$ 恒成立, 因此 $c_i\neq c_j$ ($|i-j|\geq 2$) 在大多数情况下成立, 仅在 $(b_1b_{n-2},b_2b_{n-1})$ 处可能相同.
  

以上出现了 $2n-5-1$ 个不同的数. 算上未讨论的 $b_n=n$, 得 $|Q|\geq 2n-5$.

考虑取等条件:

• $n$ 为奇数时, 考虑长度为 $\frac{n-1}{2}$ 的等比数列 $S$, 考虑 $S\cup \{0\}\cup(-S)$ 即可;
• $n$ 为偶数时, 只能取 $2n-4$. 简单讨论 $|\{c_i\}|$ 取达最小值与否即可.