奥数第三题补gap

[TheMatrix]

前尘往事。老MITBBS上做的奥数第三题，做了一个星期，最后还有一个gap，刚想出来，结果老买提down了。新买提上来了把它有个交代。

奥数第三题是这样的：给定正整数k，和一个奇素数集合，该集合中的元素如果排列成一个环路，且任意相邻元素(p,q)之间存在正整数x满足p*q=x^2+x+k的话，那么该排列不能换序，也就是说只有唯一的排序。

这个证明是这样的。还是提出这个概念：如果任意两个整数(p,q)之间存在x满足p*q=x^2+x+k的话，说p和q之间有k-联通，by x。

1. 如果两个奇素数(p,q)有k-联通by x，那么最多有一个素数m和p,q都k-联通，且m>p,q。
这个可以直接验证：
m=x_p+x_q+1
x_p = x+p
x_q = x+q
这样求出来的m，如果是素数，就是所求的素数，x_p,x_q是联通by x的x，如果不是，那么所求的素数就不存在。

2. 如果有一个素数m和两个素数p,q都k-联通，且m>p,q，那么p,q之间也k-联通。这个直接根据1验证。

有了这两个，就可以对这个素数集合排列成的环路说一些事情了：找到最大的，它两边的元素必须直连（根据2），形成一个三角形环路，那么就存在一个边数减一的环路。再找一个最大的，又可以形成一个三角形环路，大环路可以再减一。。。最后形成一个最小的三角形。也就是原环路是这样形成的：从最小的三角形环路开始，每次添加一个元素，或者说在某一边上以三角形的方式扩充一个元素，形成加一的环路。一个一个加上来，形成原环路。

我上次的gap就在这。从这个过程还不能说这个环路的顺序是唯一的。因为不能排除这种可能性：就是再添加某个素数的时候，可以有不止一个边可以添加这个素数。要排除这一点就要用到：

3. 对于一个素数m，最多存在一对素数(p,q)，使得m和p,q都k-联通，且m>p,q。这就排除了上面那种可能性。
这个证明也很简单，还是用1,2，反证法，假设存在三个素数(p,q,r)都和m联通且小于m，那么(p,q)联通，(p,r)也联通，而它们形成的m不可能一样。

这样就没有gap了。

[lasa]

欢迎回来啊

[TheMatrix]

谢谢。看见老友很高兴。

欢迎回来啊

[bce]

DEL