拿球必胜策略

mathe

从计算的角度，得到12#的结果已经非常有效了, 下面两个函数的第一个返回最后的一个h值使得$F_K(n)=F_K(n-1)+F_K(n-h)$ 所以通常只要输入的N充分大，就应该是最终的h. 第二个函数返回所有先手负的策略构成的序列。 计算结果表明通常h无法达到h(K)(见17#的定义).比如h(10)=25,但是对于K=10,好像h只能达到23.

2. gend(k,N)=
3. {
4. local(V,d);
5. V=vector(N);
6. for(u=1,k,V[u]=u);
7. d=1;
8. for(s=k+1,N,if(V[s-1]>k*V[d],d=d+1);V[s]=V[s-1]+V[d]);
9. N-d
10. }
12. genV(k,N)=
13. {
14. local(V,d);
15. V=vector(N);
16. for(u=1,k,V[u]=u);
17. d=1;
18. for(s=k+1,N,if(V[s-1]>k*V[d],d=d+1);V[s]=V[s-1]+V[d]);
19. V
20. }

复制代码

056254628

将$H_K(N)$ 的值按N从小到大按下面的方法排列，可以看出很多性质： 下面的结果是K＝3，N<1000 --------------------------- 1, --------------------------- 2, --------------------------- 3, --------------------------- 4,1, --------------------------- 6,1, --------------------------- 8,1,2, --------------------------- 11,1,2,3, --------------------------- 15,1,2,3,4,1, --------------------------- 21,1,2,3,4,1,6,1, --------------------------- 29,1,2,3,4,1,6,1,8,1,2, --------------------------- 40,1,2,3,4,1,6,1,8,1,2,11,1,2,3, --------------------------- 55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1, --------------------------- 76,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1, --------------------------- 105,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2, --------------------------- 145,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3, --------------------------- 200,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1, --------------------------- 276,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,76,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1, --------------------------- 381,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,76,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,105,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2, --------------------------- 526,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,76,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,105,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,145,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3, --------------------------- 726,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,76,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,105,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,145,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,200,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4,1,21,1,2,3,4,1,6,1,29,1,2,3,4,1,6,1,8,1,2,40,1,2,3,4,1,6,1,8,1,2,11,1,2,3,55,1,2,3,4,1,6,1,8,1,2,11,1,2,3,15,1,2,3,4, －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 性质： 1.每列的第一个数满足$H_K(N)=N$ 2.每列的除去第一个数外的所有数刚好都是$H_K(N)$数列的前d个数。d＝下一列的第一个数减去本列的第一个数再减1。d也刚好等于数列前几行的数的总数目。

056254628

因为上述排成的数列：每列第一个数都是满足先手负，并且它们是相邻的两个。 那么它们的差值＝下一列的第一个数减去本列的第一个数＝d＋1 而d＋1刚好都是某列第一个数，所以相邻的两个先手负的N的差值必然也是满足先手负的。 －－－－－－－－－－－－－－ 上贴排成的数列。从第5行开始，都满足 第m行的d值＝前m-4行的数的总数目 也就是说第m＋1个先手负的N值减去第m个先手负的N值等于第m－3个先手负的N值， 即满足f(m+1)=f(m)+f(m-3) f(n)表示所有先手负的N值组成的数列。

056254628

根据第10楼$H_K(N)$的计算式。 对于较大的数N，满足$H_K(N)=N$, 那么，其后一个$H_K(N)$值，肯定是1，后一个肯定是2，........,同我们计算第一个、第二个、......$H_K(N)$值的过程一模一样。 所以应该可以利用第10楼$H_K(N)$的计算式用数学归纳法证明22楼的性质2及2楼的式子。

056254628

$f_K(i)$:表示先手负的N值从小到大构成数列, $H_K(N)$:9楼Mathe的定义. $H_K(0)=oo$ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 将数列$H_K(N)$，按下列方式排列： 第1行：1， 第2行：2， ... 第i行：$H_K(f_K(i))$,$H_K(f_K(i)+1)$,$H_K(f_K(i)+2)$,...... －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 计算公式：$H_K(N)=min{t|1<=t<=N,H_K(N-t)>tK}$ 式1 我们只要依次判断数列第N-1，N-2，....，N-t，..，2，1项的值是否大于tk即可，从第一个满足条件就可中止判断。这时$H_K(N)=t$，如果都不满足，那么$H_K(N)=N$。 当t从1增到N，第一个满足$H_K(N-t)>tK$时，我们就称为计算到第(N-t)项处中止。 当计算所有的项都不中止，我们称为计算到第0项处中止。 性质1：如果$H_K(N)$是某行的第一个数，$H_K(N)$必定是前N项中最大的数。 性质2：计算$H_K(N)$，如果$H_K(N)$是某行的第一个数，那么它必定不在任何位置中止。 性质3：计算$H_K(N)$，如果$H_K(N)$不是某行的第一个数，那么它必定是在某中间位置(在该行的第一个数或该行第一个数和第N项之间的某位置)中止。 性质4：前k行，每行只有1个数，第i行的数等于i。 $i>=k+1$时，第i行的数的个数大于1个。 ------------------------------------- 假如我们已经排好了前i行(i>=k+1). 假设第i行一共有d+1个数。 a.那么后面的d个数必定是数列$H_K(N)$的前d个数。性质5 先用数学归纳法证明性质5： 1. 该行第2个数是1，等于$H_K(1)$。 该行第一个数是$f_K(i)>=k+1$,因为$H_K(f_K(i))>k$,所以$H_K(f_K(i)+1)=1$. 2. 假设该行第一个数后的p个数是数列$H_K(N)$的前p个数,那么该行第一个数后的第p+1个数等于$H_K(p+1)$. 如果$H_K(p+1)$不是某行的第一个数，那么我们按照式1计算$H_K(p+1)$时，必定中止在$H_K(1)$和$H_K(p)$之间的某项。而计算该行第一个数后的第p+1个数时，因为该数前p项正好是数列$H_K(N)$的前p个数，所以也会中止于同一位置，即该行第一个数后的第p+1个数等于$H_K(p+1)$。 如果$H_K(p+1)$是某行的第一个数(那么$H_K(p+1)$=p+1)，那么依照性质2，我们按照式1计算$H_K(p+1)$时，必定不在$H_K(1)$和$H_K(p)$之间的任何一项中止。而计算该行第一个数后的第p+1个数时，因为不在$H_K(1)$和$H_K(p)$之间的任何一项中止，按照性质3，它必定要在该行的第一个数处中止，所以该行第一个数后的第p+1个数等于p+1,即等于$H_K(p+1)$。 综上所述，性质5得证。 b.数列$H_K(N)$的第d+1个数必定是某行的第一个数。 性质6 等价于 d必定等于数列$H_K(N)$的前面几行的数的个数的总和。 证明：如果数列$H_K(N)$的第d+1个数不是某行的第一个数，那么$H_K(d+1)$就不是某行的最后一个数，那么它后面的数按照性质3，必定中止在$H_K(1)$和$H_K(p)$之间的某项。而我们计算第i行的第d+1个数后面的数(即下一行的第一个数)时，也必定中止在第i行的第一个数或之前，与某行的第一个数必定不在任何位置中止矛盾。 c.第i行数的数目(d+1)，满足 $d+1>=(f_K(i))/k$ 性质7 －－－－－－－－－－－－－－－－－－－－－－－ 根据性质6即可得出数列$f_K(i)$任意相邻项的差必定也在数列$f_K(i)$中。 根据性质6和性质7及性质2很容易证明12楼mathe的猜测。

mathe

楼上弄了很多性质，看着很复杂，而且感觉不严密。 我们可以如下证明对于任意整数$X$，如果存在Y使得$X=F_K(Y)$,那么$H_K(X)=X$, 不然必然存在Y使得$F_K(Y)F_K(Y)$，由归纳假设 $H_K(N+1-t)=H_K(N+1-t-F_K(Y))<=tK$,所以$H_K(N+1)>t$ 1.如果$F_K(Y)=F_K(Y)$, 1.1.如果$N+1-t>F_K(Y)$, 那么$H_K(N+1-t)=H_K(N+1-F_K(Y)-t)>tK$ 所以$H_K(N+1)=t=F_K(N+1-F_K(Y))$ 1.2.如果$N+1-t=F_K(Y)$,那么必然有H_K(N+1-F_K(Y))=N+1-F_K(Y),由于$F_K(Y)<=N+1K(N+1-F_K(Y))=tK$,所以$H_K(N+1)=t=N+1-F_K(Y)=F_K(N+1-F_K(Y))$ 2.而如果$N+1=F_K(Y+1)$, 那么对于$t=H_K(N+1-F_K(Y))=H_K(F_K(Y+1)-F_K(Y))=F_K(Y+1)-F_K(Y)=N+1-F_K(Y)$ 根据$F_K$的定义$t=F_K(Y+1)-F_K(Y)>={F_K(Y)}/K$ 于是$H_K(N+1-t)=H_K(F_K(Y))=F_K(Y)<=Kt$,所以$H_K(N+1)>t=N+1-F_K(Y)$ 而对于$N+1-F_K(Y)F_K(Y+1)-F_K(Y)>={F_K(Y)}/K$ 所以$Kt>H_K(N+1-t)$ 于是我们得出$H_K(N+1)>t$,所以$H_K(N+1)=N+1$ 归纳假设成立。

056254628

根据25楼$H_K(N)$数列的排列方法，结合它的性质6、7、2。可以很方便的构造出所有的该数列的值。 第i行第1个数是N，再从数列$H_K(N)$取前面d个数排在N后面即可完成该行的排列。 d满足以下： 取p=不小于N/k的最大整数，如果数列$H_K(N)$的第p个数不是排在某行的最后一个数，那么设该行此数后面还排有t个数，那么d=p+t. －－－－－－－－－－－－－－－－－－－－ 根据该构造数列的方法，很容易得到$f_K(i)$的递推公式： $f_K(i)$表示先手负的N值从小到大排列构成的数列。 $f_K(n)=f_K(n-1)+f_K(u([(f_K(n-1)-1)/k]))$ 其中$u(s)=min{t|t>0,f_K(t)>s}$

056254628

下面是VB语言程序 计算k条件下先手负局面f(N)的前M项： f(1) = 1 a = 0 '$[(f_K(n-1)-1)/k]$的初始值 u= 1 '$u(([(f_K(n-1)-1)/k]))$的初始值 For N = 2 To M '－－－－－－－－－－－－－－－－－－－ temp = Int((f(N - 1) - 1) / k) If temp > a Then i = u Do Until f(i) > temp i = i + 1 Loop a = temp u= i End If '以上计算$u(([(f_K(n-1)-1)/k]))$的值 '-------------------------------------- f(N) = f(N - 1) + f(u) Next N