關於考試的題

lulijie

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

lulijie

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。

lulijie

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

lulijie

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

lulijie

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

lulijie

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

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的证明，我觉得难，不知大家有没有一个巧妙的证明方法。