魔方吧·中文魔方俱乐部

标题: 關於考試的題 [打印本页]

作者: 骰迷 时间: 2009-1-21 16:37:15 标题: 關於考試的題

現做一份卷，選擇題四十題，一題有四個選擇。現每四題的答案為一組（即ABCD、BDCB等），問在同一份卷內找到同樣兩個組合的機率。
條件：所有題目被正確解答，而正確答案是隨機抽選的
可別想得太簡單了，因為第一二三四題是一組，第二三四五、三四五六題都是組合
若此題被迅速解答，則再加一問：
該卷最少多少題才能確保有兩組相同的組合？
P.S.此題的確是在考數學選擇題的卷時想出來的，順帶一提，該卷我拿了滿分

[ 本帖最后由骰迷于 2009-1-21 16:41 编辑 ]

作者: a6568056 时间: 2009-1-21 16:44:48

LZ还真是能想,智商够高的,我可做不出来

作者: 122047397 时间: 2009-1-21 16:58:15

排列与组合一起来再算机率应该要用捆绑法和高次叠序否则更加麻烦

作者: 骰迷 时间: 2009-1-21 17:01:21

跨站跨站

要是我智商高我自己就把題做出來了啊
不過考試時我粗略算了一下，你選一個組合，在卷中能找到的機會大概是十幾個巴仙
這個就算得容易多啦，呵呵

作者: latios 时间: 2009-1-21 17:03:21

沒有數錯的話應該要195題

作者: 骰迷 时间: 2009-1-21 17:25:44

LS能不能解釋一下是怎麼算的呢？只看答案可不知道過程呢～
但是共有4*4*4*4=256種組合，195題大概是不行的答案吧
頭四題是一組，往後每加一題就加一種組合，253該是座底的數字吧
但是連續的253題究竟能不能將所有的組合都數出來呢？

作者: 曾经沧桑 时间: 2009-1-21 17:30:53

晕菜，lz自己想得明白吗？

作者: latios 时间: 2009-1-21 18:06:11

原帖由骰迷于 2009-1-21 17:25 发表
LS能不能解釋一下是怎麼算的呢？只看答案可不知道過程呢～
但是共有4*4*4*4=256種組合，195題大概是不行的答案吧
頭四題是一組，往後每加一題就加一種組合，253該是座底的數字吧
但是連續的253題究竟能不能將所有 ...

好像沒有256個組合
例如
AAAA AAAB AAAC AAAD
前後倒轉的話就是
AAAA BAAA CAAA DAAA
這裡只是有7個組合而不是4X2=8個
所以好像不是單純4X4X4X4=256是吧
思考有點混亂= =

[ 本帖最后由 latios 于 2009-1-21 18:49 编辑 ]

作者: latios 时间: 2009-1-21 19:08:33

應該是256的對..

作者: juventus66 时间: 2009-1-21 19:34:37

看到这么多的高手,小弟惭愧

作者: aben306 时间: 2009-1-21 19:51:44

呵呵,到这里免费搜索答案来了.

作者: tyeken8 时间: 2009-1-21 19:55:49

有意思…有时间做做看…

作者: lulijie 时间: 2009-1-22 00:29:34

懒得想，先编个程序让电脑算算，以后再用人脑仔细算算。
用电脑模拟随机的40道题答案，共试验一百万次，其中有877838次具有所要求的相同序列。故概率大约比87%多点。
用电脑模拟随机的96道题的答案，以下序列找不到所要求的相同序列：
DADDACDDCBCDCABCDBCADDBDCAACDCDDAABCBCCDCCCCBCABBDCBADABCCABDDADAADACBAADCDABACACADBCDACCBBACDAA
故所求的最小值不可能是96.
用电脑模拟随机的97道题的答案，共试验三百万次，其中具有所要求的相同序列的情况全部出现，故97是不是所求的最小值还有待继续检验。

作者: lulijie 时间: 2009-1-22 00:50:50

4个答案为1组，比如ABCD，
第一个答案有4种可能，第二个答案有4种可能，第三个答案有4种可能，第四个答案有4种可能，故4个答案组合成1组，最多就只有4*4*4*4=256种可能。
故260个选择题，可以选择的组合数有257种，1-4,2-5,3-6,……,256-259,257-260
因为4个答案为1组的组合数最多只有256种可能，故257种选择中，必有一组相同，所以260个选择题，必然满足条件。但是，260是不是最小值，不能就这样确定。根据电脑计算，最小值必需大于96。

作者: kexin_xiao 时间: 2009-1-22 19:50:44

我来学习一下,排列组合+逻辑分析!

作者: lulijie 时间: 2009-1-22 20:27:30

今天再次用电脑模拟随机的97道题的答案，共试验一亿次，其中具有所要求的相同序列的情况仍然全部出现。
97会是最后所求的最小值吗？

作者: 骰迷 时间: 2009-1-22 20:41:35

自己終於把題目搞清楚了，汗
原來是這樣的啊
本人水平不高，只會出題，卻連題都沒搞清楚
有趣的是，不必將所有的組合都列出來，都可以肯定有兩組相同的組合
用四字成語來形容：故步自封！

作者: lulijie 时间: 2009-1-22 23:50:37

以下序列共由259个字母A、B、C、D组成的，它们找不到相同的两个组合（连续4个字母组成1个组合）
DADDACDDCBCDCABCDBCADDBDCAACDCDDAABCBCCDCCCCBCABBDCBADABCCABD
DADAADACBAADCDABACACADBCDACCBBACDAAAACBBCBDABDBCCCAADBAACCDDDD
CDCBDCCBABCAAABBBCCBDBBCACCACBCBACBDDCACDBBBBABBAAADDCCADADBBA
DCBBBDBACCCDADCADCCDBABABDACAABAABDCDBDBDDBADDDBCBBDDDABBCDDBB
DAACABADBDAD
故259不是最小值，而260已经证明必然存在相同的两个组合，故楼主所求的最小值是260。

作者: R'cube 时间: 2009-1-23 15:11:15

LZ不要什么题目都等着别人解答，自己就不能好好想想嘛，也不是十分难的题目~~~~

作者: 骰迷 时间: 2009-1-23 17:02:32

回樓上：還沒有人理會我的第一題呢

作者: lulijie 时间: 2009-1-23 19:25:24

第1道题想获得精确的概率，是非常复杂的，要考虑的情况非常多，它们还相互交织，错综复杂，一步留神，还被重复计算，造成错误，所以我认为还是用电脑模拟来得到近似值就可以了，如果大家认为87%还不够精度，那么让电脑模拟一亿次也可以，不过我觉得没多大意义。

作者: 第8个小笼包 时间: 2009-1-24 11:07:26 标题: 能不能说说你的方法

原帖由 lulijie 于 2009-1-22 23:50 发表
以下序列共由259个字母A、B、C、D组成的，它们找不到相同的两个组合（连续4个字母组成1个组合）
DADDACDDCBCDCABCDBCADDBDCAACDCDDAABCBCCDCCCCBCABBDCBADABCCABD
DADAADACBAADCDABACACADBCDACCBBACDAAAACBBCBDABD ...

这个结果我倒不是很感兴趣，反而是你怎么找出的这一串字母组合我很好奇哦

作者: lulijie 时间: 2009-1-24 14:57:41

不知你有没有注意到我上面序列长度为96时举的例子吗，它和我最后举的259长度时的例子有什么相同之处？它刚好是后面例子的前96个字母。
前96个字母组成的序列是电脑模拟随机过程时找到的。但我在模拟97个字母组成的序列时遇到了麻烦，我让电脑模拟了一亿次，花了大约20分钟时间，没找到一个例外序列（不满足所要求的条件），所以我才发出了最小值是不是97的感慨。
我无意中比较了90长度找到的例外序列与96长度找到的例外序列，惊奇的发现他们形式完全一样，把其中一个序列的A与C互换，B和D互换，90长度的例外序列就是96长度的例外序列的一部分。我突然想到只要在原序列后逐渐添加字母，让电脑检验增长后的序列是不是例外序列，（很简单，新增的序列只有4个，电脑检验非常快），得到新的增长的序列后，再往后增长，很快就到达了259，找到了我所给的序列。
没有检验程序的话，利用记事本的搜索功能，也可很快的增长序列。我们只要让记事本搜索序列的最后3个字母，序列能找到的相同之处不会多于3个，比较找到的相同处后面的字母，在序列最后加上与前不同的字母即可。若序列能找到的相同之处多于3个，那么就不可能往后增长了，那就改变方向往前增长序列。

作者: 第8个小笼包 时间: 2009-1-24 23:01:30

有没有更有规律的方法呢，我敢断言，题目即使从4选项增加到N选项，还会存在这种最大例外序列。也就是如果存在的组数小于可能的组数时，就会有例外序列。能不能解决我的疑惑呢？

作者: lulijie 时间: 2009-1-25 11:34:18

若每道选择题m个选项，N道题的答案组成一个序列，每连续的n 道题为一个组合，那么这种组合总可能数m的n 次方（记作m^n）。
那么m^n+n道题中可选择的组合数为m^n+1，故其中必有两组组合相同。
故长度为m^n+n的序列必定有两组组合相同。
若长度为N的序列中存在至少一个序列，在其中找不到两组相同的组合，那么称其为例外序列。
也就是说长度为m^n+n的序列不存在例外序列。所以必然存在一个最大长度的例外序列。
那么长度小于m^n+n的序列是不是必然存在例外序列呢？
这是需要证明的。第一种证明方法：通过排列组合加上逻辑分析，最后得出结论，是或不是。  难！
                              第二种证明方法：找到1例例外序列就可证明。对于具体的m和n值，设定程序让电脑寻找，只要找到一例就可证明。我的猜测是上述论断成立。
            也就是说长度最长的例外序列的长度为m^n+n-1。
            已知m和n，可让电脑证明。但对于一般形式的m和n的证明，我觉得难，不知大家有没有一个巧妙的证明方法。

作者: 第8个小笼包 时间: 2009-1-25 12:24:33

其实，关键问题是怎么找到这种有规律的序列，也就是如何构造数列。

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