PUZZLEUP 2015

solomon_007

newkid 发表于 2015-10-22 22:52
你中间加那个and rownum =1是不对的。

是的, lugionline 的例子已经说明了, 我的没加的但实在是太慢了...

solomon_007

lugionline 发表于 2015-10-22 18:17
3,3的时候有更大的，验证下看看

"AAA", "BAB", "ACB", "ABC", "CAC", "BBA", "CBB", "CCA", "BCC"

利用 315楼的计算 N=3

最大就是 9

以'AAA'  开头的所有行  161280  
花了 990秒

solomon_007

newkid 发表于 2015-10-22 22:50
看不出来。6个答案是多少？

是不是这样的规律阿:

2: 2/4          2^1/2^2
3: 9/27        3^2/3^3
4: 64/256    4^3/4^4
5:                5^4/5^5
6:                6^5/6^6
7:                7^6/7^7

所有 N=6 答案是 6^5=7776   我瞎猜的

lugionline

聪明，其实我也没算出7，7是多少，但是看一下左上三角部分的结果，基本能猜出结果来



我一开始说算出了6，6 是按照每个编码只差一位 (A-B, B-C) 这种计算，没有包括A-C,A-D,加上这些后边太多了

我相信答案是 M^(K-1)

lugionline

想到一个证明的思路，先来考虑 平面上的情况(长度为2，K个字符，X轴表示第一个字符，Y周表示第二个字符)

于是每个格点都表示一个可行的编码，每个点都和横向或纵向的所有点相连

选择任意一个点，这个点的所有横向纵向上的点就都不能选择了，剩下的点刚好构成一个 K-1的格点，

于是递推公式是 D[2, K] = 1 + D[2, K-1] 所以 对二维的情况 D[2, K] = K

高维的情况还没思路

newkid

lugionline 发表于 2015-10-23 10:29
想到一个证明的思路，先来考虑 平面上的情况(长度为2，K个字符，X轴表示第一个字符，Y周表示第二个字符)

...

变成一个多维的皇后问题了，有点抽象!

lugionline

看看能不能搞定高维的情况

记 K = 字符串长度, M = 字母个数(A, B, C, ...，我们实际记为 A[1], A[2], ... A[M])

先提出一个猜想：

所有 K = 2 长度 M 个字母组成的字符串可以被分成 M 组，其中每组的编码都不相似（至少差两位）

比方  对于2个字母 (AA, BB) 是一组，(AB, BA) 是一组
        对于3个字母 (AA, BB, CC) 是一组，(AB, BC, CA)是一组， (BA, CB, AC)是一组

在这个基础上可以证明，K 为任意数时，所有编码可以被分成 M 组(G[1], G[2], ... G[M])，每组的编码都不相似
        每组中的编码个数是 M^(K-1)

这步证明很容易，只需要构造M组序列
        (A[1], A[2], A[3], ... A[M])
        (A[2], A[3], ... A[M], A[1])
        (A[3], ... A[M], A[1], A[2])
        ...
        (A[M], A[1], A[2], ... A[M-1])

使用其中任意一组序列，比方 (A[1], A[2], A[3], ... A[M])
        依次取出每个字母连接到 G[1], G[2], ... G[M] 后面
可以证明这些长度为 K + 1 的字符串不相似(共 M^(K-1) * M 个)
        组内元素本来就不相似
        组与组之间元素本来至少一位不同，加上后面一位不同，所以也不相似

同时我们有M组序列，也就是同时构造出了M组，每组编码不相似

于是可以用归纳法证明K为任意数时成立

现在问题就化简为证明这个猜想了，我想应当不是很困难吧，也许只需要按我们上面构造的序列那样
        1, 2, 3  ... M  (第一排取第一个，第二排取第二个...)
        2, 3, ... M, 1
        3, ... M, 1, 2
        M, 1, 2, ...M-1

取平面格点中的每个元素就可以了（参考平面的情况）

看看有没有漏洞

solomon_007

看得还是很迷胡    

lugionline

solomon_007 发表于 2015-10-24 22:11
看得还是很迷胡

呵呵，写得比较乱，而且跳过了很多普通的结论(元素是否重复，是否就是最大解(用抽屉原理证明))，而且没有按正常证明思路描述

不管怎么样，7^6这个答案是找到了，这就足够了

newkid

lugionline 发表于 2015-10-26 07:37
呵呵，写得比较乱，而且跳过了很多普通的结论(元素是否重复，是否就是最大解(用抽屉原理证明))，而且没有 ...

我总算看懂了，果真是巧夺天工，决定送你一个章！随便挑吧。
K+1时候的抽屉原理还有点想不通，我相信再花点时间能弄懂。