结论是
\boxed{x=8}.
下面给出一个只靠逻辑枚举的严格证明:先构造一个最坏只需 8 次相邻交换的策略,再证明 7 次不可能保证成功。
- 记号与一个基本事实
把最初上层从左到右四种颜色重命名为 1,2,3,4,所以下层未知排列是 S_4 中的某个排列。
记
s_1=(1,2),\qquad s_2=(2,3),\qquad s_3=(3,4),
即分别交换第 1,2、第 2,3、第 3,4 个位置。
例如从 1234 做 s_2,得到 1324。
若已经确定目标排列,从排列 p 变成排列 q 所需的最少相邻交换数,等于二者相对次序的逆序数。下面记为 d(p,q)。
询问不计入交换次数。
⸻
- 8 次一定可行
先询问初始状态 1234 的匹配数,记为 M。
对于两个排列,不可能恰有 3 个位置相同,所以
M\in{0,1,2,4}.
下面分别处理。
⸻
情形 M=4
已经完成,交换 0 次。
⸻
情形 M=2
此时下层只能是
2134,\ 3214,\ 4231,\ 1324,\ 1432,\ 1243.
先做
1234\xrightarrow{s_1}2134.
询问。
得分 剩余可能
4 2134
0 1243
1 3214,4231,1324,1432
前两种已经确定目标;其中 d(2134,1243)=2。
若得分为 1,再做
2134\xrightarrow{s_2}2314.
此时:
得分 剩余可能
2 3214,1324
0 4231,1432
再统一做
2314\xrightarrow{s_1}3214.
若候选是 3214,1324,此时得分分别为 4,1;
若候选是 4231,1432,此时得分分别为 1,0。
所以第三次交换后一定确定下层。
而
d(3214,1324)=2,
d(3214,4231)=d(3214,1432)=4.
因此这一大情形最多需要
3+4=7
次交换。
⸻
情形 M=1
8 个可能排列为
\begin{aligned}
a&=1342,& b&=1423,& c&=3241,& d&=4213,\
e&=2431,& f&=4132,& g&=2314,& h&=3124.
\end{aligned}
先做
1234\xrightarrow{s_2}1324.
询问后恰分成两组:
\text{得分 }2:\quad {a,b,g,h},
\text{得分 }0:\quad {c,d,e,f}.
得分为 2
做
1324\xrightarrow{s_3}1342.
此时:
得分 可能
4 a=1342
0 h=3124
1 b=1423,\ g=2314
若为最后一组,再做
1342\xrightarrow{s_2}1432.
此时 b 的得分为 2,g 的得分为 0,所以确定目标。
并且
d(1432,b)=1,\qquad d(1432,g)=5.
到这里已经用了 3 次交换,所以最坏是
3+5=8.
得分为 0
从 1324 做
1324\xrightarrow{s_1}3124.
询问:
\text{得分 }1:{c,f},\qquad
\text{得分 }0:{d,e}.
再做
3124\xrightarrow{s_2}3214.
在第一对中,c,f 的得分分别为 2,0;
在第二对中,d,e 的得分也分别为 2,0。
因此总共 3 次交换后确定目标。
此时
\begin{array}{c|cccc}
q&c&f&d&e\ \hline
d(3214,q)&1&5&5&3
\end{array}
所以仍然最多
3+5=8.
因此 M=1 时最多 8 次。
⸻
情形 M=0
9 个错位排列为
2143,2341,2413,3142,3412,3421,4123,4312,4321.
先做
1234\xrightarrow{s_2}1324.
询问:
\begin{array}{c|l}
\text{得分}&\text{可能排列}\ \hline
2&4321\
0&2143,2413,3142,3412\
1&2341,3421,4123,4312
\end{array}
若为 4321,已经确定,而且
d(1324,4321)=5,
总共只需 1+5=6 次。
得分为 0
做
1324\xrightarrow{s_1}3124.
此时:
0\to2413,\qquad
2\to3142,\qquad
1\to{2143,3412}.
前两个直接确定。
若剩下一对,再做
3124\xrightarrow{s_2}3214.
2143,3412 的得分分别为 0,2,于是确定。
且二者距 3214 都为 3,因此总交换数至多 3+3=6。
得分为 1
同样先做
1324\xrightarrow{s_1}3124.
得到
0\to{2341,4312},
2\to{3421,4123}.
第一对:做 s_2 到 3214,两者得分分别为 0,1,确定目标;距目标分别为 2 和 4,所以总数至多 7。
第二对:先做
3124\xrightarrow{s_3}3142.
此时二者得分仍都为 1;再做
3142\xrightarrow{s_2}3412.
这时 3421,4123 的得分分别为 2,0,确定目标,而且
d(3412,3421)=1,\qquad d(3412,4123)=3.
总交换数至多
4+3=7.
所以 M=0 也不超过 7 次。
综上,存在一个策略对任意下层排列都在
\boxed{8}
次相邻交换以内完成。
⸻
- 为什么 7 次不可能
现在证明任何策略都不能保证 7 次完成。
只需考察初始询问结果
M=1.
此时就是刚才的 8 个排列
a,b,c,d,e,f,g,h.
第一步只能是 s_1,s_2,s_3。
由于把整个棋盘左右反射,并同时作颜色替换
1\leftrightarrow4,\qquad2\leftrightarrow3
不改变问题,所以 s_1 和 s_3 完全对称。
因此只需证明:
- 第一交换是 s_1 时,7 次不够;
- 第一交换是 s_2 时,7 次也不够。
⸻
3.1 第一交换为 s_1
来到
裁判可以回答 0,此时候选恰为
A={a,b,c,d}
={1342,1423,3241,4213}.
而这四个目标距 2134 都恰为 3。
现在还剩 6 次交换额度。
一个小引理
若在 2134,候选仍是整个 A,但只剩 4 次交换,则必败。
因为下一步只有三种:
s_1:\ 2134\to1234.
四个候选的反馈都还是 1,而
d(1234,c)=d(1234,d)=4.
只剩 3 步,因此裁判选 c 或 d 即失败。
若走
s_2:\ 2134\to2314,
裁判可回答 1,留下 {a,d},而
d(2314,a)=d(2314,d)=4>3.
若走
s_3:\ 2134\to2143,
四者反馈仍相同,而
d(2143,a)=d(2143,c)=4>3.
故引理成立。
⸻
回到还剩 6 步的状态 2134,A。
第二步若走 s_1,回到 1234,仍无新信息,只剩 5 步。
此后若走 s_2,到 1324 后裁判可留下 {c,d},其中
d(1324,d)=5,
但只剩 4 步。
若走 s_3 到 1243,四个候选仍给出相同反馈,而
d(1243,c)=5>4.
若又走 s_1 回到 2134,则只剩 4 步,正落入上面的引理。
所以第二步不能走 s_1。
第二步若走 s_3,到 2143,四个候选反馈仍相同,只剩 5 步。
下一步若 s_1 到 1243,c 距离为 5,而只剩 4 步。
若 s_2 到 2413,裁判可回答 0 留下 {a,c},且
d(2413,a)=5>4.
若 s_3 回到 2134,只剩 4 步,再由引理失败。
所以第二步也不能走 s_3。
只剩第二步走 s_2,到 2314。
裁判可回答 1,留下
{a,d}.
还剩 5 步。
但这个二候选状态本身也无法在 5 步内保证解决:
从 2314 若走 s_1 到 3214,二者已经可区分,但若目标为 d,
d(3214,d)=5,
而此时只剩 4 步。
若走 s_3 到 2341,可区分二者,但若目标为 a,
d(2341,a)=5>4.
唯一剩下的是 s_2 回到 2134。此时还有 4 步,候选为 {a,d}。下一交换无论是 s_1,s_2,s_3,裁判都可保留一个距离至少 4 的候选,而交换后只剩 3 步:
\begin{array}{c|c}
\text{走到}&\text{仍可能且距离为 4 的目标}\ \hline
1234&d\
2314&a,d\
2143&a
\end{array}
因此失败。
所以第一步若为 s_1,7 次不能保证成功。
由左右对称,第一步为 s_3 也不行。
⸻
3.2 第一交换为 s_2
来到
裁判可以回答 2,留下
P={a,b,g,h}
={1342,1423,2314,3124}.
还剩 6 步。
现在第二步有三种。
第二步走 s_1
来到 3124。
裁判可回答 1,留下
{b,g}={1423,2314}.
只剩 5 步。
下面证明这个二候选状态不能在 5 步内解决。
在 3124:
若走 s_2\to3214,两目标立即可区分,但
d(3214,b)=5,
而只剩 4 步。
若走 s_3\to3142,两者反馈仍相同,还剩 4 步。此时下一步:
1342:\ d(1342,g)=4,
3412:\ d(3412,b)=d(3412,g)=4,
3124:\ d(3124,b)=4.
交换后只剩 3 步,所以裁判总能选一个来不及到达的目标。
若从 3124 先走 s_1\to1324,两者仍不可区分,还剩 4 步。
此时走回 3124,则 b 距离 4、只剩 3 步;
走到 1342,则 g 距离 4、只剩 3 步;
唯一可能是走 s_2\to1234。此时还有 3 步,且
d(1234,b)=d(1234,g)=2.
但下一步:
s_1:\ 1234\to2134
虽能区分,却有 d(2134,b)=3>2;
s_3:\ 1234\to1243
虽能区分,却有 d(1243,g)=3>2;
s_2
又回到 1324,二者仍不可区分且距离都为 3,只剩 2 步。
故也失败。
于是第二步 s_1 不行。
第二步 s_3 完全左右对称,也不行。
第二步只能走 s_2
于是回到
1234,
候选仍是整个 P,还剩 5 步。
下一步若走 s_1\to2134,裁判回答 0,可留下
{a,b}.
这里只剩 4 步。
但 {a,b} 从 2134 无法在 4 步内保证解决:
直接走 s_2\to2314 虽能区分二者,但两目标距 2314 都为 4,只剩 3 步;
走 s_3\to2143 时仍不能区分,而且 a 距离 4,只剩 3 步;
走 s_1 回 1234 时仍不能区分,只剩 3 步,而随后三个可能交换分别会让 a 或 b 保持至少 3 的距离,交换后却只剩 2 步。
所以失败。
若在 1234 的第三步走 s_3,由左右对称同样失败。
若走 s_2\to1324,仍没有得到新信息,只剩 4 步。
此时若走 s_1,裁判可留下 {b,g},而
d(3124,b)=4>3.
若走 s_3,对称地可留下同一对并让另一个目标距离 4。
若再走 s_2 回 1234,只剩 3 步;此时:
- 走 s_1,裁判留下 {a,b},两者到 2134 距离都是 3,而只剩 2;
- 走 s_3,左右对称;
- 走 s_2,回到 1324,b,g 仍都可能且距离 3,只剩 2。
仍然失败。
所以第一步为 s_2 也无法保证 7 次成功。
⸻
因此,在初始反馈为 1 的情况下,无论第一交换选 s_1,s_2,s_3 中哪一个,裁判都有一种下层排列,使得挑战者在 7 次交换内无法保证完成。
于是
x>7.
结合前面已经构造出的 8 次必胜策略,
\boxed{\boxed{x=8}}.
也就是说:最优策略的最坏情况恰好需要 8 次相邻交换。
谷歌云俄勒冈的回答