claude code 为什么过不了糖果测试题

# 答案：x = 8



## 一、记号和三个基本事实



- 把上层杯子按初始位置从左到右记为颜色 1、2、3、4，所以上层初始是 `1234`。下层是一个未知排列 π，例如 `2431` 表示下层从左到右依次是 2、4、3、1。上层的当前排列记为 U。询问的回答是 U 与 π 相同位置上颜色相等的个数。

- s1、s2、s3 分别表示交换第 1–2、2–3、3–4 位的杯子。

- **错序数 d(U,π)**：在所有颜色对 {a,b} 中，数出在 U 和 π 里先后次序不同的对数，取值 0 到 6。d = 0 当且仅当全部配对。另记 inv(π) = d(1234, π)。



**事实 1（奇偶性）** 一次相邻交换只改变被交换的那两个颜色的先后，其他颜色对的先后都不变，所以 d 恰好变化 ±1。把 d 减 1 的交换叫前进步，d 加 1 的叫后退步。如果针对 π 一共交换了 L 次，其中 k 次是后退步，那么



  **L = inv(π) + 2k**



由此 L ≥ inv(π)，并且 L 与 inv(π) 奇偶相同。



**事实 2（确定后走最短路）** 如果 U ≠ π，按颜色在 π 中的位置重新编号后，π 变成 1234，U 不是 1234，所以 U 中一定有相邻的降序对，交换它就是一次前进步。因此一旦确定了 π，恰好用 d(U,π) 次交换就能完成。



**事实 3（信息）** 询问的答案只由 (U, π) 决定。如果两个候选排列到目前为止的所有回答都一样，挑战者就无法区分它们，只能对它们执行同一个交换序列。



---



## 二、下界：任何策略的最坏情况都至少要 8 次



只看恰好有 1 个位置初始就匹配的 8 种排列（其余三个位置是一个三轮换）：



- **P 组**（逆序数 2）：P1=`2314`，P2=`3124`，P3=`1342`，P4=`1423`

- **Q 组**（逆序数 4）：Q1=`2431`，Q2=`4132`，Q3=`3241`，Q4=`4213`



即使事先告诉挑战者 π 在这 8 种之中，他掌握的信息只会更多，所以只要证明这种情况下仍然做不到最坏 8 次以内，原题就更做不到。



这 8 种排列的逆序数都是偶数，由事实 1，它们的总交换次数一定是偶数。所以"不超过 7 次"等价于"不超过 6 次"。下面用反证法：假设能在 6 次以内完成。



由 L = inv + 2k ≤ 6 得到每个排列允许的后退步数（下文称为配额）：**Q 组最多 1 次，P 组最多 2 次**。某个候选的配额一旦用完，只要它还没被区分出来，之后每一步都必须对它是前进步。



第一步只有 s1、s2、s3 三种选择。



### 情形 A：第一步是 s2（上层变成 1324）



询问结果是 P 组都答 2，Q 组都答 0。对手让 π 落在 Q 组。



Q1 和 Q4 中颜色 2 都在 3 的左边，所以这一步对它们是后退步，配额已经用完。接下来在 1324：



- s1 把 3 换到 1 的左边。Q4 中 1 在 3 的左边，所以这是后退步，不行。

- s3 把 4 换到 2 的左边。Q1 中 2 在 4 的左边，所以这是后退步，不行。

- s2 把上层撤回到 1234。这一步对 Q2 和 Q3 是后退步（它们中 3 在 2 的左边），于是四个 Q 的配额全部用完。回到 1234 后询问必然答 1，没有新信息。



在 1234 再走任何一步都会让某个 Q 后退：



- s1：对 Q2 是后退步（Q2 中 1 在 2 的左边）

- s2：对 Q1 是后退步

- s3：对 Q3 是后退步（Q3 中 3 在 4 的左边）



所以情形 A 矛盾。



### 情形 B：第一步是 s1（上层变成 2134）



各排列的回答是：`2314`、`3124`、`2431`、`4132` 答 2，其余四个答 0。对手选答 2 的一组 {P1, P2, Q1, Q2}。这一步对 P2 和 Q2 是后退步（它们中 1 在 2 的左边），所以 Q2 的配额已经用完，P2 用了 1 次。



在 2134 的三种走法：



| 走法                  | 结果                                                                                                                                                                |

| --------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------- |

| s2（3 换到 1 的左边） | 对 Q2 是后退步，不行                                                                                                                                                |

| s1 撤回到 1234        | 对 P1、Q1 是后退步，Q1 用完。1234 处询问答 1，没有信息。此时 Q1、Q2 都已用完：s1 让 Q2 后退，s2 让 Q1 后退，只能走 s3 到 **1243**。这一步让 P1、P2 后退，两者也用完 |

| s3 到 2143            | 对 P1、P2 是后退步，P2 用完。2143 处四个候选都答 1，没有信息。此时 P2、Q2 用完：s2 让 P2 后退，s3 让 Q2 后退，只能走 s1 到 **1243**。这一步让 P1、Q1 后退，全部用完 |



两条路都到达 1243，四个候选的配额都用完了，而且 1243 处询问四者都答 0，仍然无法区分。在 1243 再走一步：



- s1：对 P2 是后退步

- s2：对 P1 是后退步

- s3：对 Q2 是后退步



所以情形 B 矛盾。



### 情形 C：第一步是 s3



定义镜像变换 φ：把排列左右颠倒，再把颜色 c 换成 5−c。φ 满足：



- 保持 1234 不变；

- 保持每次询问的答数不变；

- 把 s1 和 s3 互换；

- 把这 8 个排列映射到它们自身。



因此，以 s3 开头的 6 步以内策略经过镜像，就是以 s1 开头的 6 步以内策略，与情形 B 矛盾。



**结论**：这 8 个排列无法保证在 6 次以内完成，由奇偶性也无法在 7 次以内完成，所以 **x ≥ 8**。



---



## 三、上界：一个最坏 8 次的策略



1. 询问，记答数为 a。a = 4 则结束。

2. 执行 s2（上层变成 1324），询问得 b。

   - b = 4：结束，π = 1324。

   - (a,b) = (2,0)：π = 4231。

   - (a,b) = (0,2)：π = 4321。

3. 其他情况执行 s1（上层变成 3124），询问得 c。

   - c = 4：结束，π = 3124。

   - (a,b,c) = (1,2,0)：π = 1342。

   - (0,0,2)：π = 3142。

   - (0,0,0)：π = 2413。

4. 剩下 8 组，每组 2 个候选。

   - (0,1,2) 组 {4123, 3421}：执行 s3 到 3142（两者都答 1），再执行 s2 到 3412。答 2 是 3421，答 0 是 4123。

   - 其余 7 组：执行 s2 到 3214 后询问，同组两个候选的答数都不同（见下表），即可确定。

5. 确定 π 后按下表路线走完。每一步都是相邻交换，读者可以逐步核对。



| π        | 询问答数      | 确定时位置（已用次数） | 后续路线                       | 总次数 |

| -------- | ------------- | ---------------------- | ------------------------------ | ------ |

| 1234     | 4             | —                      | —                              | 0      |

| 1324     | 2,4           | —                      | —                              | 1      |

| 4231     | 2,0           | 1324（1）              | →3124→3214→3241→2341→2431→4231 | 7      |

| 4321     | 0,2           | 1324（1）              | →3124→3214→3241→3421→4321      | 6      |

| 3124     | 1,2,4         | —                      | —                              | 2      |

| 1342     | 1,2,0         | 3124（2）              | →1324→1342                     | 4      |

| 3142     | 0,0,2         | 3124（2）              | →3142                          | 3      |

| 2413     | 0,0,0         | 3124（2）              | →1324→1234→2134→2143→2413      | 7      |

| 3214     | 2,1,2,**4**   | —                      | —                              | 3      |

| 2134     | 2,1,2,**1**   | 3214（3）              | →2314→2134                     | 5      |

| 1243     | 2,1,0,**1**   | 3214（3）              | →3124→1324→1234→1243           | 7      |

| 1432     | 2,1,0,**0**   | 3214（3）              | →3124→1324→1342→1432           | 7      |

| 2314     | 1,2,1,**2**   | 3214（3）              | →2314                          | 4      |

| **1423** | 1,2,1,**0**   | 3214（3）              | →3124→1324→1234→1243→1423      | **8**  |

| **4213** | 1,0,0,**2**   | 3214（3）              | →2314→2134→2143→2413→4213      | **8**  |

| 2431     | 1,0,0,**0**   | 3214（3）              | →2314→2341→2431                | 6      |

| 3241     | 1,0,1,**2**   | 3214（3）              | →3241                          | 4      |

| **4132** | 1,0,1,**0**   | 3214（3）              | →3124→3142→3412→4312→4132      | **8**  |

| 4312     | 0,1,0,**1**   | 3214（3）              | →3124→3142→3412→4312           | 7      |

| 2341     | 0,1,0,**0**   | 3214（3）              | →2314→2341                     | 5      |

| 3412     | 0,0,1,**2**   | 3214（3）              | →3124→3142→3412                | 6      |

| 2143     | 0,0,1,**0**   | 3214（3）              | →2314→2134→2143                | 6      |

| 3421     | 0,1,2,1,**2** | 3412（4）              | →3421                          | 5      |

| 4123     | 0,1,2,1,**0** | 3412（4）              | →4312→4132→4123                | 7      |



表中 24 种排列全部列出，最大值是 8，所以 **x ≤ 8**。



---



## 四、结论



在这个策略下，每种排列都能完成配对，最坏情况需要 **8** 次交换；前面也证明了任何策略都做不到 7 次或更少。所以最少的最坏交换次数是 **x = 8**。



补充一点：如果能直接看到下层，最坏只需要 6 次（排列 4321 的逆序数）。多出来的 2 次是获取信息的代价。取到 8 次的三个排列都属于"只有 1 个位置初始匹配"那一类，这与下界的证明一致。