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

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,

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,

lulijie

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

lulijie

当所有18个点度为2时，共有18条边，移除度为2的6个点之后，最坏情况是移走了12条边，还剩6条边满足题意。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
按照这个思路来思考：
假设18个点，有17条连接线，按照最优策略来算，应该是有16个点每个2度（连有2条连接线），另两个点每个1度。
移除6个点，最坏的情况，移走的都是2度的点，但是否总共移走了12条连接线呢？如果这6个点内部有连接线，那么移走的总连接线就少于12条。那么剩下的连接线就不少于6条。
－－－－－－－－－－－－－－－
18个点，有17条连接线，任意选择6个点，是否无论你如何选择这6个点，一定存在内部（指这6个点之间）的连接线。
若存在某种连接法，使得上述的命题一定成立，那么18场就不是最少值了。
如果以下命题成立，那么18场就是最小值。
18个点，有17条连接线（任意连接方式，每个点最多2度），总能选到2度的6个点，这6个点之间不存在连接线。

lulijie

第一题的答案C(2n+1,n)确实够简洁，楼主的化简方法确实巧妙。