12 3 4 5 下一页

查看: 206296|回复: 45

最长的例外序列，求证。 [复制链接]

lulijie

红魔

Rank: 4

积分: 1194
帖子: 924
精华: 6
UID: 44804
性别: 保密

电梯直达

1^#

发表于 2009-1-25 11:52:00 |只看该作者 |倒序浏览

若每道选择题有m个选项，N道题的答案按顺序组成一个序列。每连续的n 道题为一个组合，若某一个序列，在其中找不到两组相同的组合，那么称其为例外序列。（比如4道题为一个组合，那么第1-4题的答案为一组合，第2-5题的答案也是一个组合）
求证：例外序列的最大长度为m^n+n-1。
本人还不会证明，发一贴，希望集思广益，能有所突破。
------------------------------------------------------------------------------------------------
有些人看不懂这个题目，我就换一种等价的方法来描述，或者先看看n=m=4的特例情况，骰迷的帖子
http://bbs.mf8-china.com/viewthread.php?tid=20414&;extra=page%3D2
有一个字符串S，由m种字符组成，若它上面的任何长度为n的子字符串都不相同，那么这个字符串S就称为m*n型的例外字符串，
求证：m*n型的例外字符串的最大长度为m^n+n-1 。

[ 本帖最后由 lulijie 于 2009-2-5 22:37 编辑 ]

收藏0

使用道具举报

汪小光

红魔

我小名叫耶稣

Rank: 4

积分: 1169
帖子: 983
精华: 0
UID: 38952
性别: 男

2^#

发表于 2009-1-25 11:58:09 |只看该作者

不懂……等强人解释一下

魔方魔方，我是小光，收到请回答！

使用道具举报

R'cube

红魔

沉沦一生

Rank: 4

积分: 2607
帖子: 2298
精华: 3
UID: 34403
性别: 男

3^#

发表于 2009-1-25 12:01:30 |只看该作者

做板凳观望了~~~~~~~

I'm sure you'll do what you have to!

使用道具举报

haohejiao

红魔

Rank: 4

积分: 1018
帖子: 977
精华: 0
UID: 49503
性别: 男

4^#

发表于 2009-1-25 12:03:28 |只看该作者

哈哈地板等等 ~~~~~~~~

使用道具举报

R'cube

红魔

沉沦一生

Rank: 4

积分: 2607
帖子: 2298
精华: 3
UID: 34403
性别: 男

5^#

发表于 2009-1-25 12:52:14 |只看该作者

貌似没人来解答难题啊

I'm sure you'll do what you have to!

使用道具举报

juventus66

铜魔

Rank: 8 Rank: 8

积分: 8483
帖子: 7887
精华: 0
UID: 68944
性别: 男

6^#

发表于 2009-1-25 13:27:45 |只看该作者

惭愧,不会啊~~~~

使用道具举报

骰迷

红魔

All Blue

Rank: 4

积分: 1196
帖子: 999
精华: 2
UID: 38845
性别: 男

7^#

发表于 2009-1-25 16:27:15 |只看该作者

樓主好像很喜歡另外開帖哈
頂一下

使用道具举报

第8个小笼包

白魔

Rank: 1

积分: 92
帖子: 72
精华: 1
UID: 68405
性别: 保密

8^#

发表于 2009-1-26 00:02:10 |只看该作者

把已经找到的例外数列首位相接，应该能称为一个例外的环。我真的不会这个题目，希望能有高手教教。

使用道具举报

lulijie

红魔

Rank: 4

积分: 1194
帖子: 924
精华: 6
UID: 44804
性别: 保密

9^#

发表于 2009-1-31 11:49:27 |只看该作者

8楼的环的概念很赞。
长度为256的由ABCD四个字母组成的首位相接的环，从环上任意截取连续的4个字母为一个组合，再截取另一个组合（按相同方向排列，比如都是顺时针）。求证必然存在一个环，在它上面不存在两种相同的组合，我们把它叫做例外环。若存在例外环，一共有几个例外环？

以下长度259的例外序列：
DADDACDDCBCDCABCDBCADDBDCAACDCDDAABCBCCDCCCCBCABBDCBADABCCABD
DADAADACBAADCDABACACADBCDACCBBACDAAAACBBCBDABDBCCCAADBAACCDDDD
CDCBDCCBABCAAABBBCCBDBBCACCACBCBACBDDCACDBBBBABBAAADDCCADADBBA
DCBBBDBACCCDADCADCCDBABABDACAABAABDCDBDBDDBADDDBCBBDDDABBCDDBB
DAACABADBDAD

若去掉尾部与头部相同的3个字母，首尾相接，组成长度256的环。但它不是例外环。
----------------------
看错了，它是例外环，但一共有几个例外环呢？，字母ABCD互换位置，也是例外环。

[ 本帖最后由 lulijie 于 2009-1-31 13:01 编辑 ]

使用道具举报