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

superacid

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

这句话是关键

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

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

superacid

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

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

noski

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

superacid

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

lulijie

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

superacid

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