好久没发题了...(第一题解答新鲜出炉)

lulijie

设n步中有m步是沿y轴方向，那么有n-m步沿x轴方向。那么方案有 C(n,m) * 2^(n-m) * f(0,m)
              用f(y,m)表示从纵坐标y出发，沿y轴方向走m步，不走到x轴以下的总方案数。C(n,m)表示n中取m的组合。
总路线数等于对上述的式子求和，即＝∑ C(n,m)*2^(n-m)*f(0,m)        m=0 to n
－－－－－－－－－－－－－－－－－－－－－－－
对于f(y,m) 有以下递推公式：
f(y,m) = f(y+1,m-1)+f(y-1,m-1)
计算f(y,m) 结果如下：
          y=0,1,2,3,4,......
m=0：1,
m=1：1,2,
m=2：2,3,4,
m=3：3,6,7,8,
m=4：6,10,14,15,16,
m=5：10,20,25,30,31,32,
m=6：20,35,50,56,62,63,64,
m=7：35,70,91,112,119,126,127,128,
m=8：70,126,182,210,238,246,254,255,256,
m=9：126,252,336,420,456,492,501,510,511,512,
m=10：252,462,672,792,912,957,1002,1012,1022,1023,1024,
m=11：462,924,1254,1584,1749,1914,1969,2024,2035,2046,2047,2048,
m=12：924,1716,2508,3003,3498,3718,3938,4004,4070,4082,4094,4095,4096,
m=13：1716,3432,4719,6006,6721,7436,7722,8008,8086,8164,8177,8190,8191,8192,
m=14：3432,6435,9438,11440,13442,14443,15444,15808,16172,16263,16354,16368,16382,16383,16384,
m=15：6435,12870,17875,22880,25883,28886,30251,31616,32071,32526,32631,32736,32751,32766,32767,32768,
m=16：12870,24310,35750,43758,51766,56134,60502,62322,64142,64702,65262,65382,65502,65518,65534,65535,65536,
观察上述结果得  f(y,m) 的结果如下：
   f(y,m)=2^m                            y>=m
   f(m-i,m)=f(m-i+1,m)-c(m,(i-2)/2)      i为偶数  
   f(m-i,m)=f(m-i+1,m)-c(m,(i-1)/2)      i为奇数
解得：
   m为偶数  f(0,m)=2^m-2*∑ c(m,i)                  i=0 to (m-2)/2
   m为奇数  f(0,m)=2^m-2*∑ c(m,i) -c(m,(m+1)/2)    i=0 to (m-3)/2
  即
   m为偶数  f(0,m)=c(m,m/2)            
   m为奇数  f(0,m)=c(m,(m-1)/2)  
-------------------------------------------
   总路线数＝∑ C(n,m)*2^(n-m)*C(m,int(m/2))       m=0 to n     int()为取整函数
用该公式计算n从1 到16，得结果如下：
3,10,35,126,462,1716,6435,24310,92378,352716,1352078,5200300,20058300,77558760,300540195,1166803110,

superacid

楼上数据是对的...
还有，第二题的答案没有这么大吧...

[ 本帖最后由 superacid 于 2009-8-3 21:49 编辑 ]

noski

这18个小组3个3个分成六大组，每个大组的3个成员之间赛三场，一共要赛18场；
或者，这18个小组组成一个环，18条边就是赛18场，也可以满足条件。
18场，不知是否有反例或者还可以更少。。

lulijie

13#的方案：18个小组3个3个分成六大组，每个大组的3个成员之间赛三场，一共要赛18场；
可以证明是必然满足条件的。
若12个人刚好每个大组选2人，那么每个同组的之间有1场比赛，6个组刚好6场。
若某组中只有1人被选中，必然有另一大组被选中3人，总共比赛数就会增加1场。

lulijie

第一题也可以改为，只能行进在第一象限中（包括x、y的正轴线）：
    那么  总路线数＝∑ C(n,m)*C(n-m,int((n-m)/2))*C(m,int(m/2))       m=0 to n     int()为取整函数
n从1计算到16，结果如下：
2,6,18,60,200,700,2450,8820,31752,116424,426888,1585584,5889312,22084920,82818450,312869700,

superacid

为什么你一定要这么分组？
是否存在其他的方法使得少于18场？

Cielo

C₁₈¹² x 6 ≤ C_18-2^12-2 x n
得到 n ≥ 17，估计要证明 n = 17 不行吧……

lulijie

楼上17#的不等式，解得结果应该是n>= 6*(18*17)/(12*11)=13.9
    即n>=14吧。

superacid

话说那天考联赛当中休息时，我们同学三个人一起边散步边讨论这道题，然后，都进冬令营了...

noski

其实第二题“18个点中选12个点，至少共包含6条边”，也就是“18个点中取走6个点，至少还剩6条边”，这与每个顶点的度有关。
最佳分配策略是：初始每个点的度都是0，一条边一条边的加，直到所有点的度都变成1，继续加边，直到所有点的度都变成2……；
最坏情况取数策略是：不断移除度最大的点；
当所有18个点度为2时，共有18条边，移除度为2的6个点之后，最坏情况是移走了12条边，还剩6条边满足题意。
不妨顺着这个思路试一下：
F（18，17，6）＝7
F（18，16，6）＝8
F（18，15，6）＝9
F（18，14，6）＝14
F（18，13，6）＝16
F（18，12，6）＝18
……