拿球必胜策略

mathe

定理1.$H_K(N)=min{t|1<=t<N/{K+1}" or "t==N,H_K(N-t)>tK}$
定理2.$H_K(M)=M>=K,M<N<M+M/K$,那么$H_K(N)=H_K(N-M)<N$
定理3.如果$H_K(N)>sK$，那么$H_K(N+s)<=s<N+s$

mathe

猜测：如果$H_K(M)=M$,那么下一个满足$H_K(N)=N$的整数N是满足
${(N>=M+M/K),(H_K(N-M)=N-M):}$
的最小整数

mathe

12#的猜想我对$K<=10,N<=10^10$都验证通过。

mathe

我们定义数列$F_K(n)$如下
$F_K(n)=n (1<=n<=K+1)$
对于$n>K+1$,定义$F_K(n)=min{F_K(n-1)+F_K(n-h)|F_K(n-h)>={F_K(n-1)}/K}$。
性质1:
对于$n>=K+1$,如果$F_K(n+1)-F_K(n)=F_K(n-h)$,那么$F_K(n+2)-F_K(n+1) in {F_K(n-h),F_K(n-h+1)}$
证明：
显然$F_K(n)$是n的单调增数列
$F_K(n-h-1)<{F_K(n)}/K<{F_K(n+1)}/K$,所以$F_K(n+2)-F_K(n+1)>=F_K(n-h)$
$F_K(n-h+1)>=F_K(n-h)+{F_K(n-h)}/K={K+1}/KF_K(n-h)$
$K*F_K(n-h+1)>=(K+1)F_K(n-h)=F_K(n-h)+F_K(n)=F_K(n+1)$
于是$F_K(n-h+1)>={F_K(n+1)}/K$
所以$F_K(n+1)-F_K(n)<=F_K(n-h+1)$
于是得到证明

mathe

特征方程辅助定理1:
对于正整数$h>=2$,方程$x^h-x^{h-1}-1=0$有唯一的正根$r_h$,而且$r_h>1,lim_{h->+infty}r_h=1$，$r_h$关于h单调减
证明很简单，记$f_h(x)=x^h-x^{h-1}-1$,那么$f'_h(x)=hx^{h-1}-(h-1)x^{h-2}$,所以在$x>0$有唯一极小值点$x={h-1}/h$,而$f_h(0)=-1<0,f_h(1)=-1<0,f_h(+infty)=+infty$,所以$f_h(x)$有唯一正跟$r_h>1$
由于$r_h^h=1+r_h^(h-1)$
所以$r_h^{h+1}=r_h+r_h^h>1+r_h^h$
即$f_{h+1}(r_h)>0$
所以$r_{h+1}<r_h$,数列$r_h$单调减，有下界1，极限存在。
如果$lim_{h->infty}r_h=r*>1$
那么对于任意h,必然有$r_h>r*>1$
于是我们知道$f_h(r*)<0$,也就是$r*^h<r*^{h-1}+1$
或者说$r*<1+r*^{1-h}$,让$h->+infty$得出$r*<=1$矛盾
所以必然极限为1.

mathe

现在根据特征方程辅助定理1，我们得知，对于任意K,存在$h(K)$使得$r_{h(K)}>1+1/K$但是$r_{h(K)+1}<1+1/K$.
于是我们可以有定理
$F_K(n)-F_K(n-1)>=F_K(n-h(K))$
这个定理说明如果12#的猜想成立，那么必然2#的猜想也成立

mathe

给定上面这些信息以后，我们可以用数学归纳法证明12#中的猜想，
其中，对于$F_K(n)$和$F_K(n+1)$之间的数X，很容易验证$H_K(X)=H_K(X-F_K(n))$
然后通过缩放可以得出1和${F_K(n+1)}/{K+1}$之间没有满足条件的t(主要有一部分$F_K(n+1)-t$要小于$F_K(n)$,这个只要证明$F_K(n-1)$和$F_K(n)$之间所有数的$H_K$函数的值都不超过$F_K(n-h_n)$就可以了，但是计算有点麻烦

wayne

mathe神人也
在世高斯也

mathe

过奖了。这个题目难点在猜测结果，至于后面的证明实际上我没有完成，只是感觉应该不难了，所以没有继续下去。至于高斯，他那个时代没有计算机，倒是猜测结果有点困难

KeyTo9_Fans

好像是08年ACM/ICPC北京赛区的题目，不知道楼主在这里有没有稍作更改。

我参加过这场比赛，对这道题有一点点印象。

我队先用简单的方法把小规模的数据全部打印出来研究，然后找到了规律，最终在比赛结束前12分钟完美解决此题。