關於考試的題

骰迷

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

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

第8个小笼包

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

lulijie

若每道选择题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个小笼包

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

lulijie

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

第8个小笼包

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

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

lulijie

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

骰迷

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

R'cube

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

lulijie

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