果树问题讨论：这两个问题等价么？呵呵。

zgg___

用这个标题的帖子火了，所以我也用这个标题来一帖。呵呵。
首先和大家分享一个游戏吧。
规则是这样子滴：我们想要将一个升序序列经过一些置换操作变成一个降序序列。
容许的操作有：1、如果相邻的2个是从小到大的，可以置换成从大到小的，叫P2操作；2、如果相邻的3个是从小到大的，可以置换成从大到小的，叫P3操作；……
举些例子吧。
例如：如果要将1234567置换成7654321，可以是如下的过程：
1234567
3214765
3274165
3724615
7364251
7634521
7654321
可以看到，其中用了5次P3操作，6次P2操作。（5*3+6*1=7*6/2）
如果我们希望尽可能多的运用P3操作，我们会发现下面的过程是更优的：
1234567
3214657
3264157
3624751
3674251
7634521
7654321
看，我们做了6次P3操作呢。可以发现对于长度为7的序列，最多只能做6次P3操作。我们定义这种现象为G(7,3)=6。
经过尝试，可以发现G(8,3)=7，而G(9,3)=10，下面把G(9,3)的过程演示一下：
ABCDEFGHI
CBAFEDIHG
CBFAEIDHG
CBFIEADHG
CIFBEHDAG
ICFHEBDGA
IHFCEGDBA
IHFGECDBA
IHGFEDCBA
这10个P3操作分别是ABC-DEF-GHI-AEI-BFI-ADH-BEH-CFH-BDG-CEG。（恩，看上去眼熟呢。）

总结一下，我们要将长度为n的序列通过各种P操作来逆序，并且试图使Pm操作的次数最大化，定义这个最大次数为G(n,m)。

这个游戏是不是有些无聊呢？我可是费了好大的力气才编出这个游戏的呢。呵呵。
说了这么多，那么两个问题是什么呢？

问题一：G(20,4)是几?

问题二：20棵树，4个一行，最多几行？

最后扣题：这两个问题等价么？呵呵。

litaoye

应该不等价

（原因详见http://bbs.emath.ac.cn/thread-703-1-1.html 二楼）

zgg___

2# litaoye
为什么不等价呢？呵呵。
我觉得挺等价的哟。呵呵。

litaoye

3# zgg___

主要是为了让这个帖子和上个帖子更像！不过现在已经不像了！呵呵！

mathe

是挺相似的。不过没有理由等价。倒是可以同那一边的问题一再比较比较

shshsh_0510

呵呵，亏你编的出。
这个问题妙就妙在它象那边的问题2
如果真等价，那会是个很了不起的观察

shshsh_0510

你这个感觉位于那两个问题之间
那个问题1 是组合几何，问题2是射影，而你这个描述了拓扑位置关系，应该比问题2弱一些

zgg___

我一直再琢磨如何不用数值运算（例如加减乘除），仅仅单纯通过某种逻辑上的关系来计算或判断共点线的关系。
在尝试几何定理的抽象、点线相互生成等等方法没有结果之后，前一段时间突然想到的这种方法的。

那么两个问题的差别在哪里呢？

首先，可以看到，可以存在的共点线关系（在问题二中）一定对应于某种置换关系（在问题一中）。
就是说如果我们可以穷举G(20,4)，我们一定不会漏掉20棵树的答案的。所以我们或许可以尝试着搜索一下。

反过来。

可以看到，某个大个的P操作是可以分解成为一些更细小的P操作的。例如：1个P3可以分成3个P2，1个P4可以分成1个P3和3个P2。而共点线关系不一定容许。
例如：在1楼那个G(9,3)的例子中，如果我们硬要把DEF的P3操作分解成为DE、DF和EF这3个P2操作，那么是不对应几何上的共点线关系的。
而我觉得两个问题的差别仅在于此。如果我们能够避免这种分解，我觉得两个问题就等价了。而我们争取使Pm操作的次数最大化的过程，恰好可以抑制这种分解。

总之，我倾向于两问题是等价的。

此外，对于搜索G(20,4)，蛮力的数据量是很大的。我想可以可虑深度优先的搜索。20个点，相当于190次P2。1个P4相当于6个P2。我们知道存在23*P4+52*P2的置换过程，我们试图找到24*P4+46*P2的过程。我想可以先深度较浅的搜索一下（这里深度的定义是已有P4数量*6+已有P2数量），统计出从递增序列开始，k次P2（比方说k取1到50）最多可以合成多少P4，这个数量与深度为190-k的时候（此时还剩k次P2的机会）还能再获得P4的最大数量是一样的，如果数量不够就可以剪枝了。

mathe

>>>首先，可以看到，可以存在的共点线关系（在问题二中）一定对应于某种置换关系（在问题一中）。
这个不一定吧

zgg___

>>>首先，可以看到，可以存在的共点线关系（在问题二中）一定对应于某种置换关系（在问题一中）。
这个不一定吧
mathe 发表于 2009-12-2 11:40

这个是一定的。可以用构造的方法来证明。
假设共点线关系是存在的，我们总可以：
1、按照共点线关系，在地上画出这些点，画出这些点之间的所有连线，并且使这些连线都不平行。（目的仅是为了排除无穷远点的干扰。）
2、建立直角坐标系，使x轴和y轴和上面提到的连线都不平行。
3、按照这些点y坐标的大小，标记上与y坐标大小相应的字母，这些字母就是所要置换的序列。
4、设想一个人站在x轴的负无穷的位置（就是x值足够负的位置），他从右向左观察各点上的字母，这些点构成一个递增序列。
5、然后他沿着x轴向正的方向前进，同时记录各个字母排列位置的变化。他每当通过一条连线，这些字母就进行了一次Pm操作，m值就是这条连线所通过的点的数量。
6、当他通过所有直线，快到x轴的无穷大时，序列就完成了逆序。

通过证明可以看到，其实这个序列如果构成头尾相接的环形，结论也是成立的。我们也可以考虑置换一个环上的序列，这样所有的组合就减少了很多，或许在搜索中可以更有效。但是问题可能就更不容易说清，所以我一开始也就没有这么提，呵呵。