使用带锁盒子的传递模型

Rratic

这个模型的二人版本是在《十日终焉》看到的,最早来源未知。它可以扩展到一般的任意 n 人情形。

大致的背景设定是这样的:现在有 n 个人分别在各自的房间中,一个人希望向另一个人传递信息(一张纸条)。他们唯一的交流方式是通过一个不可信的、能够在房间之间移动的使者。为了防止纸条被使者偷看,考虑把纸条放在盒子中,给盒子上锁。

一开始每个房间里有一把锁和一个钥匙,全部的 n 把锁和 n 个钥匙是相对应的;此外某个房间里有盒子,某个房间里有纸条。我们希望最终能够达成要求一:让每个人都看到信息。

一个变体是达成要求二:一个指定的人收集到所有的锁和钥匙。这里未上锁的盒子中放的东西可能被使者拿走。

以下通过给出几个操作的构造。其中大写字母表示锁,小写字母表示钥匙,盒子表示为 [contents]{locks}.


先展示两人情形是如何做到的:

操作
初始状态A, b 与盒子Ba
上锁b[]{A}Ba
传递bB, a[]{A}
解锁整理b[Aa]{B}
传递b[Aa]{B}/
解锁整理所有物品/

这里无论信息一开始在谁手上,都能做到让另一个人看到。


现在把这个情形推广。假设一开始盒子在甲手上,并且甲房间中锁和钥匙不相对应。

不妨标记甲手上是锁 B 和钥匙 a, 去看谁手上有钥匙 b. 不妨设是乙,手上是锁 C 和钥匙 b; 这样进行下去必然回到甲,不妨设轮到的最后一个人是癸,手上是锁 A 和钥匙 z. 我们称这些人构成初始圈,说明最终可以由甲回收初始圈的所有物品。

操作
初始状态B, a 与盒子CbNEXTthisAz
上锁a[]{B}CbNEXTthisAz
传递并整理a[Bb]{C}NEXTthisAz
传递并整理(归纳)a//A, z[BbCc...Yy]{Z}
传递并整理所有物品///

由于可以在最开始的时候传递空盒子给指定的人,如果所有人都在初始圈中,那么要求一、要求二均可达成(但不一定有方案同时达成)。


现在考虑所有人分成多个圈的情形(一个圈可以只有一人)。

对要求二,先进行之前的操作,然后参考以下流程:

操作
初始状态A, B, a, b 与盒子XyYx
上锁并传递abX, y[B]{A}Yx
上锁并传递a, b[B]{AX}yYx
解锁并传递A, abyY, x[B]{X}
解锁整理A, aby[BXx]{Y}
传递并整理A, ab[XxYy]{B}/
传递并整理所有物品//

注意这个过程中用到了甲配有两套锁与对应的钥匙。