生日悖论外传的外传:差分序列与贪心算法

昨天,matrix67大牛在博客上出了这么一道题

把 n 拆分成 n1 + n2 + … + nk ,使得 C(n1 , 2) + C(n2 , 2) + … + C(nk , 2) 正好等于 C(n, 2) 的一半。[…]看上去,问题的解似乎很没规律, n = 8 时竟然无解想必会让不少人大吃一惊,而 n 是某些质数时却反而有不少解,这使得问题变得非常有趣。是否能找到一种构造解的方法,从而说明问题有无穷多解?解的个数与 n 之间存在什么关系?能否找到一种生成全部解的方法?这个问题之前有研究过吗?得出过什么有趣的结论吗?欢迎大家在下面一起来讨论。

下面给出解的存在性的一个证明。

我们先将问题扩展到,对于任意整数m,求序列n1, n2, …, nk,使得C(n1 , 2) + C(n2 , 2) + … + C(nk , 2)=m。令S(m)=min( n1 + n2 + … + nk | C(n1 , 2) + C(n2 , 2) + … + C(nk , 2) =m)。

定义如下的贪心算法:

ALG(m):
if(m=0) return 0;
let i = max( i | i (i – 1) / 2 <= m, i>0);
return i + ALG(m – i(i-1)/2);

简单来说,这个算法就是每次挑选最接近m的二项式系数\binom{i}{2},然后选择这个系数成为分拆的一部分,如此递归下去。

显然有ALG(m) \ge S(m)。为了给S(m)一个上界,我们尝试给ALG(m)一个上界。

根据ALG的定义,我们有递推关系:

ALG(m) = k + ALG( m - \binom{k}{2})

其中\frac{k(k-1)}{2} \le m < \frac{k(k+1)}{2}

我们希望有ALG(m) \le c\sqrt{m} + O(1)。显然对于m比较小的时候,可以用O(1)的部分应付过去。只需要证明这个不等式可以通过递推关系就行了(其中保持O(1)的部分不变)。

代入递推关系,得:(注意到\binom{k}{2} \le m<\binom{k+1}{2},也就是说m-\binom{k}{2} \le k-1

ALG(m) \le k +c\sqrt{m-\binom{k}{2}} + O(1) \le k+c\sqrt{k-1}+O(1)

而我们希望有ALG(m) \le c\sqrt{m} + O(1),由于O(1)项的关系(这要求S(m)对于小的m的存在性,这由C(2,2)=1得到),于是只需要对足够大的k有如下的不等式即可:

k+c\sqrt{k-1} \le c\sqrt{m}

m\ge \binom{k}{2}收紧条件,只需要有:

k+c\sqrt{k-1}\le c\sqrt{\frac{k(k-1)}{2}}

再次收紧条件:k+c\sqrt{k}\le c\sqrt{\frac{k(k-1)}{2}}

化简得:\sqrt{k}+c\le c\sqrt{\frac{k-1}{2}}

易知,当c > \sqrt{2} 时,上述不等式成立,我们有想要的结果。从而这个关于ALG(m)的上界可以传递到S(m)上。于是我们有:

S(m) \le c\sqrt{m} + O(1), c > \sqrt{2}。其中O(1)项可以通过上面的不等式成立时的最小值来计算。

在上式中取m=\frac{1}{2}\binom{n}{2},易知

{m} \le \frac{n(n-1)}{4} < (\frac{n}{2})^{2}

而我们想要证明S(m) \le n。于是,只需要取\sqrt{2} < c < 2,即可证得,对于足够大的n,原题总有解。

而实际上,通过ALG(m)的图像,我们可以知道,对于n \ge 50,我们明显有ALG(m) < 2\sqrt{m}。由于matrix67已经求出n<50的所有解,所以我们可以断言,对于所有n \equiv 0,1 \mod 4,除了5,8,12外,原问题均有解,而且可以通过上述的贪心算法给出解。

实际上,如果我们仔细观察上面的证明,我们可以看出来,通项为C(k,2)这一点无关紧要,它唯一的作用就是用相邻两项的差作出上界来推动归纳法,所以可以替换为任意对于充分大的k满足ak+1-ak<=k的数列(an),还有包含1为其中一项。另外,容易看出,只要单调递增正整数列(an)的差分序列(an+1-an)有关于n的一个多项式的一个渐近上界的话,也可以得到类似的结果(实际上,这个条件相当于要求数列有一定的密度,当然这时S(m)的上界就不同了)。由此可以得到一大批定理,虽然可能大部分都比较平凡而无新意。

Advertisements

3 thoughts on “生日悖论外传的外传:差分序列与贪心算法

  1. 没看懂啊,为什么 S(m)<=n 就能说明原问题有解?存在 n1 +…+ nk < n 使得 C(n1 , 2) + … + C(nk , 2) = m 并不能说明存在 n1 +…+ nk = n 使得 C(n1 , 2) + … + C(nk , 2) = m 吧。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s