Steven_MengのBlog

一个非常有趣的结论:

$Raney$引理:

给你一个数列$\{a_i\} (1 \le i \le n)$,而且定义$S_i=\sum _{i=1}^n a_i$,并且$S_n=1$,求证$\{a_i\}$的循环排列里面有且仅有一个序列,满足$\forall i \in [1,n],S_i > 0$。

循环排列的意思也非常好理解。

举一个例子:$a=\{1,4,-5,3,-2,0\}$

循环排列为:

  1. $<1, 0 4, -5, 3, -2,>$
  2. $<4, 1 -5, 3, -2, 0,>$
  3. $<-5, 3, -2, 0, 1, 4>$
  4. $<3, -2, 0, 1, 4, -5>$
  5. $<-2, 0, 1, 4, -5, 3>$
  6. $<0, 1, 4, -5, 3, -2>$

显然对于这组数据来说,$4$是满足条件的。

如何证明?

看到这类环上的问题,首先考虑拆环成链。

考虑一个无限的数列$b=\{a_1,a_2,a_3,…a_n,a_1,a_2,a_3,…a_n,a_1,a_2…\}$

对于这个数列,再做一次前缀和,设$f_x=\sum _{i=1}^x a[i]$

注意到$f_{x+n}-f_x=f_n=1$,所以这个函数每过$n$格就会整体向上平移一格:

资料来源:浅谈数形结合思想在信息学竞赛中的应用

可以看图理解。

于是我们可以构造斜率为$\frac{\dfrac$的两条直线”夹住”原函数。

可以发现每过$n$个点,下面那条直线就会和函数相切一次。

从那个切点(图中为$(3,0)$)向上走,发现所有的$S_i$都$>0$,因为函数不可能和下面的直线相交。

同时在每$n$个点中,有且仅有一个点和直线相切(因为每过$n$个点函数才会经过一次整点),这就证明了唯一性。

思考,$S_n!=1$时,为什么不能说明唯一性?

因为$S_n!=1$时,斜率为$\fra\dfrac}{n}$,不能保证一定只经过一个整点。

比如$S_n=2,n=6$时,就会发现会有矛盾。

 评论