[组合] 集合元素个数,群里看到的

(35.79 KB)

2013-1-7 16:12

虽然已经有答案,第一眼觉得不错,保留在这里
唐山齐老师:
http://zhidao.baidu.com/question/492222198.html,搜到个解答

____kuing edit in $\LaTeX$____
给定整数 $n>1$，设 $a_1$, $a_2$, $\ldots$, $a_n$ 是互不相同的非负实数，记集合
\[A=\{a_i+b_i|1\leqslant i\leqslant j\leqslant n\}, B=\{a_ia_j|1\leqslant i\leqslant j\leqslant n\}.\]
求 $\frac{\abs A}{\abs B}$ 的最小值。这里，$\abs X$ 表示集合 $X$ 中元素的个数。

1楼连接中的解答
pighead520| 四级  
首先：$|A|_{min}=2n-3$ 这是因为：为方便起见，将an做一个排序 即  $a_i>a_j>0, (i>j)$这样 $a_1+a_1<a_1+a_2<……<a_1+a_n<a_2+a_n<……<a_{n-1}+a_n<a_n+a_n$   这里共有2n-1个数      而且$|A|=2n-1$ 可以取到（递增的等差数列就能满足）|B|的最大值就是每两个数的乘积都不相同$|B|=\frac{n(n+1)}{2}$    所以$\frac{|A|}{|B|}$的最小值就是$\frac{4n-2}{n^2+n}$
最好能加一个$|B|=\frac{n(n+1)}{2}$的实例,怎么构造呢?

令等差数列为$a_n=1+n\sqrt{2}$
若$a_pa_q=a_sa_t,p\ge{q},s\ge{t}$,那么代入通项公式有$p+q=s+t,pq=st$,可得$p=s,q=t$
所以任意两项乘积互不相同

nice

话说最大值如何？|B| 最小似乎还能上面那个还小，因为可以有0

最大模仿2楼那个网友pighead520做法,{$b_k$}为递增,$1\ge{k}\ge{n-1}$,但另外加个$b_n=0$,
那么非零的有$b_1b_1<b_1b_2<b_1b_3<...<b_1b_{n-1}<b_2b_{n-1}<....<b_{n-1}b_{n-1}$包括0,共2n-2项,前$n-1$项为等比即符合题意.
和最大个数为$\frac{n(n+1)}{2}$,实例是$b_k=\sqrt{2}3^{k-1}$,$k=1,2,...,n-1$,$b_n=0$,
p<q<n,s<t<n,若$b_p+b_q=b_s+b_t$,假定$p<s$,两边约去$\sqrt{2}3^p$后,矛盾==,
最大就是$\frac{n(n+1)}{4n-4}$