发信人: longriver (大河), 信区: BrainTeaser
标 题: 提问：“二十五匹马”的变形
发信站: BBS 未名空间站 (Mon Jan 12 20:09:48 2009)

原题是说：二十五匹马，每次可以挑五匹马跑，只记名次不能计时，问需要多少次才能
找出最快的三匹马

变形一：如果每次跑的五匹马不是由你指定，而是完全随机产生，平均下来需要跑多少
次？

变形二：每次跑得马还是随机产生，不过能够保证相同的五匹马不会跑第二次，平均下
来需要跑多少次？
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问：“二十五匹马”的变形
发信站: BBS 未名空间站 (Wed Jan 14 11:49:00 2009)

//faint，连个Re都没有
太容易了大家不屑，还是太难了没有思路？

我的思路是，先跑一个模拟程序，看看结果如何
不过没有想明白如何给定了一堆跑的结果下分析跑得最快的三匹
对问题二来说，答案最小是7，最大是C(25,5)，就是每五匹马都跑一遍
最终的expectation肯定落在之间
我希望模拟程序能够跟出一个大致的答案
下一步再进行理论分析

大家觉得呢？

【 在 longriver (大河) 的大作中提到: 】
: 原题是说：二十五匹马，每次可以挑五匹马跑，只记名次不能计时，问需要多少次才能
: 找出最快的三匹马
: 变形一：如果每次跑的五匹马不是由你指定，而是完全随机产生，平均下来需要跑多少
: 次？
: 变形二：每次跑得马还是随机产生，不过能够保证相同的五匹马不会跑第二次，平均下
: 来需要跑多少次？



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问：“二十五匹马”的变形
发信站: BBS 未名空间站 (Tue Jan 20 20:31:14 2009)

longriver, seems to me the problem is hard. and i agree monte carlo is
probably the only way to go, though it does not seem straightforward either.
let me know if you come up with a nice solution.

btw, just for reference, there was some discussion here of some other
generalization of the original problem:
http://wilmott.com/messageview.cfm?catid=26&threadid=64478
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.135.]