问题：
› 有一个水杯配对游戏。共有 4 种不同颜色的水杯，每种颜色各有两个。将同色的两个水杯分别放在上下两层，因此
上下两层各有 4 个水杯。下层 4 个水杯按某个未知顺序排列，挑战者无法看到它们；上层水杯的颜色和位置则完
全可见。游戏开始后，挑战者可以反复进行以下操作：
向裁判询问当前有多少个位置满足“上下两个水杯颜色相同”。裁判只回答匹配位置的总数，不透露具体是哪些位置；
根据目前获得的所有信息，挑战者可以选择交换上层任意两个相邻位置的水杯，注意只能是相邻，不能是任意两个。
当 4 个位置全部匹配时，游戏结束。问题：
挑战者应采用何种策略，才能保证对于下层水杯的任意排列都能完成配对？
所有能保证成功的策略中，最坏情况所需的交换次数最少是多少？
回答时请不要进行联网搜索，也不要写代码来辅助计算(包括思考过程中)。
假设答案是 x ，你需要给出严格的证明，为什么 x 可行，为什么小于 x 不可行。
回答：
• 设上层初始排列为 (1234)。把下层排列记为一个置换 (p)。一次交换就是把当前排列右乘一个相邻换位
(s_1=(12),s_2=(23),s_3=(34))。询问所得数值为当前排列 (q) 与 (p) 在相同位置上的个数。
答案是
[
\boxed{x=6}.
]
下界
考虑下层排列为 (4321)。
初始排列 (1234) 到 (4321) 的相邻交换距离等于逆序数：
[
\operatorname{inv}(4321)=6.
]
每次操作只能交换相邻位置，因此无论询问得到什么信息，最终上层排列要变成 (4321)，至少需要 (6) 次交换。所以
[
x\ge 6.
]
上界
下面说明 (6) 次交换总能完成。
询问初始排列 (1234) 的匹配数，记为 (k)。
- (k=4)：已经完成。
- (k=3)：不可能出现，因为一个置换不可能恰有三个不动点。
- (k=2)：下层排列必为一个换位。
- (k=1)：下层排列恰有一个不动点。
- (k=0)：下层排列是一个无不动点置换。
先交换第 (1,2) 个位置，得到
[
2134,
]
再次询问。
对于 (k=0) 的情况，所有无不动点置换为
[
2143,\ 2341,\ 2413,\ 3142,\ 3412,\ 3421,\ 4123,\ 4312,\ 4321.
]
将它们与 (2134) 比较，匹配数分别为
[
2,1,1,1,1,1,1,1,0.
]
因此若初始询问为 (0)，第二次询问为 (0)，就唯一确定下层是 (4321)。此时沿着
[
2134\to2314\to2341\to3241\to3421\to4321
]
继续交换五次即可，总计六次。
集合 (C) 时，保证完成所需的最少最坏交换次数。若尝试相邻交换 (s_i)，询问结果为 (r)，则候选集合变为
[
C_{i,r}
={p\in C:\operatorname{match}(qs_i,p)=r}.
]
于是有递推式
[
D(C,q)
\min_{i=1,2,3}
\left(
1+\max_r D(C_{i,r},qs_i)
\right),
]
并且 (D({q},q)=0)。
把 (24) 个置换逐一列出并按上式直接核验，可得：
[
\begin{array}{c|c}
\text{初始匹配数 }k & \text{第一次交换后最坏还需交换数}
\hline
0&5
1&5
2&4
\end{array}
]
因此：
- 初始匹配数为 (0) 时，先交换一次，之后最多再交换五次；
- 初始匹配数为 (1) 时，先交换一次，之后最多再交换五次；
- 初始匹配数为 (2) 时，先交换一次，之后最多再交换四次；
- 初始匹配数为 (4) 时无需交换。
所以任意下层排列都能在至多
[
1+5=6
]
次交换内完成配对。
结合下界 (x\ge6)，得到
[
\boxed{x=6}.
]
^-^
^-^
1952444901 08-31 18:151楼
suxi 08-31 18:242楼
luca123 08-31 18:263楼
1767655110 08-31 18:365楼