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

superacid

1.在平面直角坐标系的原点处有一个小虫，它每一步可以沿平行于坐标轴的方向走一个单位长度，但它不会走到x轴的下面。
现在这小虫走了n步，问它走的路线有多少条？

2.有18支球队参加友谊赛，一直任意两个球队之间至多比一场比赛，任意12支球队之间至少进行6场比赛。
问：友谊赛至少进行了多少场比赛？


公布第一题答案C(2n+1,n)，方法见24楼。

[ 本帖最后由 superacid 于 2009-8-7 15:53 编辑 ]

superacid

后面的那种做法太强了，我也想不到。

lulijie

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

superacid

终于写完了...蛮辛苦的

noski

晕，算起来这么复杂的题，答案竟然这么简洁

superacid

第一题答案是C(2n+1,n)，可以从lulijie11楼的∑C(n,m)*2^(n-m)*C(m,[m/2])得出（我就是这么做出来的）

[ 本帖最后由 superacid 于 2009-8-7 15:52 编辑 ]

superacid

今天还没有人做出的话，明天就公布答案了。

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个点之间不存在连接线。

superacid

“其实第二题“18个点中选12个点，至少共包含6条边”，也就是“18个点中取走6个点，至少还剩6条边”，这与每个顶点的度有关。”

这句话是关键

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
……