使用带锁盒子的传递模型
Rratic
这个模型的二人版本是在《十日终焉》看到的,最早来源未知。它可以扩展到一般的任意 n 人情形。
大致的背景设定是这样的:现在有 n 个人分别在各自的房间中,一个人希望向另一个人传递信息(一张纸条)。他们唯一的交流方式是通过一个不可信的、能够在房间之间移动的使者。为了防止纸条被使者偷看,考虑把纸条放在盒子中,给盒子上锁。
一开始每个房间里有一把锁和一个钥匙,全部的 n 把锁和 n 个钥匙是相对应的;此外某个房间里有盒子,某个房间里有纸条。我们希望最终能够达成要求一:让每个人都看到信息。
一个变体是达成要求二:一个指定的人收集到所有的锁和钥匙。这里未上锁的盒子中放的东西可能被使者拿走。
以下通过给出几个操作的构造。其中大写字母表示锁,小写字母表示钥匙,盒子表示为 [contents]{locks}.
先展示两人情形是如何做到的:
| 操作 | 甲 | 乙 |
|---|---|---|
| 初始状态 | A, b 与盒子 | B 与 a |
| 上锁 | b 与 []{A} | B 与 a |
| 传递 | b | B, a 与 []{A} |
| 解锁整理 | b | [Aa]{B} |
| 传递 | b 与 [Aa]{B} | / |
| 解锁整理 | 所有物品 | / |
这里无论信息一开始在谁手上,都能做到让另一个人看到。
现在把这个情形推广。假设一开始盒子在甲手上,并且甲房间中锁和钥匙不相对应。
不妨标记甲手上是锁 B 和钥匙 a, 去看谁手上有钥匙 b. 不妨设是乙,手上是锁 C 和钥匙 b; 这样进行下去必然回到甲,不妨设轮到的最后一个人是癸,手上是锁 A 和钥匙 z. 我们称这些人构成初始圈,说明最终可以由甲回收初始圈的所有物品。
| 操作 | 甲 | 乙 | … | 癸 |
|---|---|---|---|---|
| 初始状态 | B, a 与盒子 | C 与 b | NEXT 与 this | A 与 z |
| 上锁 | a 与 []{B} | C 与 b | NEXT 与 this | A 与 z |
| 传递并整理 | a | [Bb]{C} | NEXT 与 this | A 与 z |
| 传递并整理(归纳) | a | / | / | A, z 与 [BbCc...Yy]{Z} |
| 传递并整理 | 所有物品 | / | / | / |
由于可以在最开始的时候传递空盒子给指定的人,如果所有人都在初始圈中,那么要求一、要求二均可达成(但不一定有方案同时达成)。
现在考虑所有人分成多个圈的情形(一个圈可以只有一人)。
对要求二,先进行之前的操作,然后参考以下流程:
| 操作 | 甲 | 壬 | 癸 |
|---|---|---|---|
| 初始状态 | A, B, a, b 与盒子 | X 与 y | Y 与 x |
| 上锁并传递 | a 与 b | X, y 与 [B]{A} | Y 与 x |
| 上锁并传递 | a, b 与 [B]{AX} | y | Y 与 x |
| 解锁并传递 | A, a 与 b | y | Y, x 与 [B]{X} |
| 解锁整理 | A, a 与 b | y | [BXx]{Y} |
| 传递并整理 | A, a 与 b | [XxYy]{B} | / |
| 传递并整理 | 所有物品 | / | / |
注意这个过程中用到了甲配有两套锁与对应的钥匙。