拿球必胜策略

mathe

定理1.$H_K(N)=min{t|1<=ttK}$ 定理2.$H_K(M)=M>=K,MsK$，那么$H_K(N+s)<=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}infty}r_h=r*>1$ 那么对于任意h,必然有$r_h>r*>1$ 于是我们知道$f_h(r*)<0$,也就是$r*^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分钟完美解决此题。