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

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