IBM Ponder This #168 · 2012 年 4 月

本题采用 Harry Buhrman、Serge Fehr、Christian Schaffner 与 Florian Speelman 在论文 http://arxiv.org/abs/1109.2563 中提出的 garden-hose 模型。

Alice 只知道五位二进制数 X，Bob 只知道五位二进制数 Y，两人要判断 X 是否等于 Y。他们之间有八根水管，每根一端在 Alice 侧，另一端在 Bob 侧。各人可依据自己的输入，用软管把本侧两个管口配对连接，每个管口最多参与一个连接。Alice 还可把水龙头接到本侧一个未配对的管口。

接好后放水，水最终只会从其中一侧流出。要求当且仅当 X=Y 时，水从 Alice 一侧流出。

把水管标作 A 至 H，水龙头标作 T。为每个五位输入给出两人的连接方法，共 32 行，每行用冒号分隔 Alice 与 Bob 的字母对列表。两边放在同一行只是为了简写，并不意味着任何一方知道对方输入。

一个一位输入版本的例子是：

TA,CH:AB
TG,EF:DG,EF

官方 4 月 10 日补充的两位输入例子：

TA BC DE:AF
TB AC ED:BG
TC AB DE:CH
TD AE BC:FD

解答

认真尝试后再打开

待补充。