从计算的角度，得到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.
gend(k,N)=
{
local(V,d);
V=vector(N);
for(u=1,k,V=u);
d=1;
for(s=k+1,N,if(V>k*V,d=d+1);V=V+V);
N-d
}
genV(k,N)=
{
local(V,d);
V=vector(N);
for(u=1,k,V=u);
d=1;
for(s=k+1,N,if(V>k*V,d=d+1);V=V+V);
V
}
本帖最后由 056254628 于 2010-9-9 22:50 编辑
将$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也刚好等于数列前几行的数的总数目。
因为上述排成的数列：每列第一个数都是满足先手负，并且它们是相邻的两个。
那么它们的差值＝下一列的第一个数减去本列的第一个数＝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值组成的数列。
根据第10楼$H_K(N)$的计算式。
对于较大的数N，满足$H_K(N)=N$,
那么，其后一个$H_K(N)$值，肯定是1，后一个肯定是2，........,同我们计算第一个、第二个、......$H_K(N)$值的过程一模一样。
所以应该可以利用第10楼$H_K(N)$的计算式用数学归纳法证明22楼的性质2及2楼的式子。
$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的猜测。
楼上弄了很多性质，看着很复杂，而且感觉不严密。
我们可以如下证明对于任意整数$X$，如果存在Y使得$X=F_K(Y)$,那么$H_K(X)=X$,
不然必然存在Y使得$F_K(Y)<X<F_K(Y+1)$,那么这时必然有$H_K(X)=H_K(X-F_K(Y))$
我们可以使用数学归纳法证明。
我们已经知道对于$X<=K+1$假设成立
现在设对于$X<=N$假设都成立，那么对于$X=N+1$,
设$F_K(Y)<X=N+1<=F_K(Y+1)$,
那么对于任意t, $1<=t<H_K(N+1-F_K(Y))<=N+1-F_K(Y)$,
必然有$N+1-t>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)<N+1<F_K(Y+1)$,
而对于$t=H_K(N+1-F_K(Y))$,同样$N+1-t>=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+1<F_K(Y+1)$,
根据$F_K$的定义，$N+1-F_K(Y)<{F_K(Y)}/K$（不然必然有$F_K(Y+1)=F_K(Y)+N+1-F_K(Y)=N+1$)
于是$H_K(N+1-t)=H_K(F_K(Y))=F_K(Y)>K(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)<t<N+1$
于是$0<N+1-t<F_K(Y)$,所以$H_K(N+1-t)<F_K(Y)$
而$t>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 于 2010-9-10 19:48 编辑
根据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}$
下面是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