受小K姐姐启发，也发一道WS的智力题

我可以给出一个2n-2的通解（3v3时即为4套套解），全选可见

-----------------------------------------------
标记方法如下：
男人记为M1, M2, M3, ...，写于左侧
女人记为F1, F2, F3, ...，写于右侧
套套用右括号)表示，被使用过的面标记该人的标号，简便起见，只记数字

n=2时的解法记为如下
--------------
STEP 1:
M1 1)- -)1 F1
--------------
STEP 2:
M1 1)2 F2
M2 2)1 F1
--------------
STEP 3:
M2 2)1 1)2 F2
--------------

将n=2扩展到n=3，即新增一男一女，各发一新套套
这两人需要相互XX并分别与原有异性XX，共1+4次
首先将下列步骤添加至STEP 1末尾：
M3 3)- -)3 F3
M3 3)- -)1 F1
M1 1)- -)3 F3
然后将下列步骤添加至STEP 2末尾：
M3 3)2 F2
M2 2)3 F3
可以看到，加入的步骤完全不影响到原有的步骤

继续扩展到n=4，增加一男一女两套套和1+6次XX
将下列步骤添加至STEP 1末尾：
M4 4)- -)4 F4
M4 4)- -)1 F1
M4 4)- -)3 F3
M1 1)- -)4 F4
M3 3)- -)4 F4
将下列步骤添加至STEP 2末尾：
M4 4)2 F2
M2 2)4 F4
可以看到，新加入的步骤仍然不影响原有步骤

继续类推，从n=i-1扩展到n=i的方法为
将下列步骤添加至STEP 1末尾：
Mi i)- -)i Fi
------------------
Mi i)- -)1 F1
Mi i)- -)3 F3
Mi i)- -)4 F4
...
Mi i)- -)i-1 F(i-1)
------------------
M1 1)- -)i Fi
M3 3)- -)i Fi
M4 4)- -)i Fi
...
M(i-1) i-1)- -)i Fi
可认为此阶段是无污染阶段
每人都有自己的套套，可以任意XX无限制

将下列步骤添加至STEP 2末尾：
Mi i)2 F2
M2 2)i Fi
可认为此阶段是有污染阶段
一方是无套套的M2或F2，另一方是有自己套套的异性
此阶段只能做2n-2次

STEP 3阶段为结束阶段
由无套套的M2和F2直接进行，可使用2阶段所用过的任意一对套套
此阶段只能做1次

此即为2n-2的通解

进一步的优化我实在是想不出来了……

42# Jawley
cool!确实有一对男女是不需要套套的。互相xx的时候用前面的套套换个顺序就可以了。

42# Jawley
cool!确实有一对男女是不需要套套的。互相xx的时候用前面的套套换个顺序就可以了。
Koizumi 发表于 2010-3-31 13:00

如何才能找到更优解法或者证明更优解法不存在？{:4_84:}

如何才能找到更优解法或者证明更优解法不存在？{:4_84:}
Jawley 发表于 2010-3-31 13:10

下次组会再讨论吧。

我打酱油了。围观数字之美
想到了上次水田里讨论的最稳定couple问题……

我打酱油了。围观数字之美
想到了上次水田里讨论的最稳定couple问题……
zach 发表于 2010-3-31 17:19

噢？结论是啥？看看我和gg稳定不，哈哈

zach当斑竹吧，把这些个智力题弄个tag啥的。

噢？结论是啥？看看我和gg稳定不，哈哈
RehsuR 发表于 2010-3-31 23:42

唔，那个帖子找不到了……
但是那个是说n男n女每个人有一个preference list，怎么找最稳定的组合的问题。你搞不到你gg/你自己/你gg社交圈/你自己社交圈的list，没法判断的……
大致意思说是，如果在你的所有potential mates里，有你觉得比你gg更好的option，同时那个option也觉得你比他目前的mm好，你俩就很有可能走到一起，你和你gg的关系就不stable咯。

唔，那个帖子找不到了……
但是那个是说n男n女每个人有一个preference list，怎么找最稳定的组合的问题。你搞不到你gg/你自己/你gg社交圈/你自己社交圈的list，没法判断的……
大致意思说是，如果在你的所有potent ...
zach 发表于 2010-3-31 23:51

这个问题很耳熟嘛，我之前看过一篇文章讨论这个问题的最优算法。
感兴趣的可以看这里。