魔方吧·中文魔方俱乐部

标题: 好久没发题了...(第一题解答新鲜出炉) [打印本页]

作者: superacid 时间: 2009-8-3 09:06:30 标题: 好久没发题了...(第一题解答新鲜出炉)

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

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

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

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

作者: lernem 时间: 2009-8-3 09:10:11

我猜一个啊 3^n条

作者: mofangPYH 时间: 2009-8-3 09:16:32

是~~~~~~~~n（n+1）条吗？~~~~~~~~

作者: superacid 时间: 2009-8-3 09:17:54

显然是不对的......

作者: islandsea 时间: 2009-8-3 09:39:27 标题: 第二个题目我知道！

从第一个队分别和其它十七个队比赛：17场——他们就可以走了！
剩下的十七支队里，再挑一支出来与其它十六阶比，就是：16场！
以此类推！

最后的场次为：17+16+15+……+3+2+1=153

作者: islandsea 时间: 2009-8-3 09:44:06 标题: 第一题的题目说的不是太清楚！

是不是可以理解为小虫子就在X轴上爬？把X轴看做是一根竹竿一样？

那就不叫什么平面直角坐标系了，因为没有Y轴啊？

小虫的行进方向只是X正向和X反向两个方向吧？

那答案就应该是2^N(二的N次方）吧？

[ 本帖最后由 islandsea 于 2009-8-3 09:48 编辑 ]

作者: 井心 时间: 2009-8-3 09:44:38

是3*2^（n-1）吧？

作者: noski 时间: 2009-8-3 11:40:09

还是先算算这个简单一点的问题：
小虫只能在Y轴正半轴上前进，每一步可以沿Y轴的方向走一个单位长度，但不可以走到原点下方。
那么，小虫从原点0出发，走n步（n为偶数）又回到原点0的路线有多少条？

-----------------------------
越看它越像随机过程中的Markov链，估计会有较好的算法吧-_-

-----------------------------
第二题，又想了一下，算出个43场。

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

作者: superacid 时间: 2009-8-3 12:18:37 标题: 回复 6# 的帖子

坐标轴有两个方向：x轴方向和y轴方向

作者: superacid 时间: 2009-8-3 12:19:46 标题: 回复 5# 的帖子

问的是至少......

作者: lulijie 时间: 2009-8-3 20:45:32

设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 时间: 2009-8-3 21:44:29

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

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

作者: noski 时间: 2009-8-3 22:33:54 标题: 回复 12# 的帖子

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

作者: lulijie 时间: 2009-8-3 22:46:49

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

作者: lulijie 时间: 2009-8-3 23:11:46

第一题也可以改为，只能行进在第一象限中（包括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 时间: 2009-8-4 15:01:43 标题: 回复 14# 的帖子

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

作者: Cielo 时间: 2009-8-4 16:38:18

C[sub]18[/sub][sup]12[/sup] x 6 ≤ C[sub]18-2[/sub][sup]12-2[/sup] x n
得到 n ≥ 17，估计要证明 n = 17 不行吧……

作者: lulijie 时间: 2009-8-4 19:40:24

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

作者: superacid 时间: 2009-8-4 20:35:59

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

作者: noski 时间: 2009-8-4 21:46:55

其实第二题“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
……

作者: superacid 时间: 2009-8-4 21:50:13 标题: 引用楼上

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

这句话是关键

作者: lulijie 时间: 2009-8-4 22:25:49

当所有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 时间: 2009-8-5 17:03:07

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

作者: superacid 时间: 2009-8-6 18:07:37

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

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

附件: 第一题.rar (2009-8-7 15:52:51, 42.54 KB) / 下载次数 10
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjI2Mjd8NjE5MWQ2NTh8MTc0MDc4NjI3OXwwfDA%3D

作者: noski 时间: 2009-8-6 19:33:52 标题: 回复 24# 的帖子

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

作者: superacid 时间: 2009-8-7 15:53:48

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

作者: lulijie 时间: 2009-8-7 17:23:35

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

作者: superacid 时间: 2009-8-7 17:36:20 标题: 回复 27# 的帖子

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)