IBM Ponder This #253 · 2019 年 5 月

一条船每次最多载两人，八个人要全部从河的一岸到另一岸。可以规定哪些人不能被一起留在岸上。设计限制，使最短的可行渡河方案也至少需要 73 次航行。

用 32 位十六进制数给出限制，它表示 128 个比特，每个比特对应其余七人的一个子集与第八人同岸的配置，1 表示禁止。

六人例子是三对家长与孩子 A、B、C、a、b、c：任何孩子若与别人的家长同岸，其自己的家长也必须在场。最短需要十一趟，其二十二个合法岸上集合如下：

...... abcABC
...ABC abc...
.bcABC a.....
a.cABC .b....
ab.ABC ..c...
.bc.BC a..A..
a.cA.C .b..B.
ab.AB. ..c..C
a..ABC .bc...
.b.ABC a.c...
..cABC ab....
11 of them contain "a":
abcABC
abc...
ab.ABC
ab.AB.
ab....
a.cABC
a.cA.C
a.c...
a..ABC
a..A..
a.....

对应的十一种互补分割编号为 31、24、23、22、16、15、13、8、7、4、0。这些位为 0，其余为 1，得到 01111110001111100101111001101110，即 7e3e5e6e。六人版本还存在最短需要十九趟的限制。

另一个八人示例，十六进制数 4672616e63657320452e20416c6c656e 对应最短十三趟。

附加问题：这个示例藏着一个名字，她在截至原题发表时共有十九人的某份名单中排第六。能列出整份名单吗？因题目较难，官方在 5 月 27 日将截止时间延后一个月。

解答

认真尝试后再打开

待补充。