对这个问题感兴趣的读者可以先暂停在这里，思考一下这个问题的答案。

--------------剧透预警--------------

让我们对这个问题进行一步步的分析。

首先，答案为  是不可能的，因为最后一个人如果看到前  个人背后的数字为  ，也无法区分自己背后的数字是  还是  。最后一个人已经无法保证自己能够回答正确。

 的答案是比较容易构造的：如果只有两个人，这两个人可以通过某种提前商量好的协议，后一个人给前一个人传话，保证前一个人能够知道自己背后的数字。比如: 如果剩余数字为。后一个人看到前一个人是就报，看到就报，看到就报。对于 个人的情况，将相邻的两人分组即可。

那么 行不行呢？首先没有人知道最后一个人背后的数字，也就是说如果答案是，那么前面的个人都需要保证报对。但是因为数字不能重复，所以第个人只能在 ta 看不到的两个数字里面二选一，来提供 1bit 信息。好巧不巧的是，对于前面个人的每个人来说，假设的人全部报对，那么第个人所要面临的选择也是二选一。而的人有必须报对的要求所以不能提供额外信息量。理论上，第个人提供的信息量又刚好抵消掉第个人需求的信息量。但如果成功达成“正确信息的传递”，面临的困难是第个人提供的信息需要恰好同时是前面每一个人需要的。这就需要信息结构保证第 个人给前面任何一个人传递的信息都是完全相关的。

对于一般的问题来说，这个要求看起来很强甚至是不可能完成的，然而对这个特殊的问题来说，解开这把锁的钥匙就藏在标题里。

回到标题，我们不妨回顾一下逆序数的基本定义和性质。对于一个长度为  的数列  ，  ，其逆序数 其主要性质如下：

(1) 交换  ，  的奇偶性改变；

(2) 交换  ，  的奇偶性改变。

直观证明如下：对于 (1)，交换  会使得逆序数在  这一项上+1或-1，因此奇偶性改变; 对于 (2)，注意到交换  可以由  次相邻交换得到，且  为奇数，因此奇偶性改变。

大部分读者可能和我一样，对逆序数唯二的接触就在于：

1) 大一上学期的线性代数（或高等代数），仅在矩阵的行列式的原始定义中用到了逆序数，然而并没有人会用原始定义去算行列式；

2) 大学前两年的编程课上，需要设计算法用  的时间计算长度为  的数列的逆序数。

当然也有可能因为笔者本人才疏学浅的缘故，逆序数在某些领域真的发挥了很大的作用，欢迎在评论区补充。

有了逆序数和对应的性质之后，定义第  个人的策略如下：

令  是 ta 看到的前面人的数，  是 ta 听到的后面人报的数。

声明：  ，  各不相同。

此时，第  个人能够确认  个数不是自己身上的数，定义 计算  和  

两者必恰好一奇一偶（因为对序列交换了  和  ）。若前者为偶，输出  ，否则，输出  。

下面证明，该策略的声明永远成立，并且保证前 个人正确回答。设前个人的数字为。定义由对称性，不妨假设第个人回答，且为偶。归纳证明：时， ，且声明为真。

假设对  的情况已经得到证明，考虑  的情况，此时应有  ，  必然互不重复，因此声明为真。

此时，玩家  会计算  ，  。

由于第  个人的策略保证了  为偶，因此玩家  一定会输出  。

这道题的证明本身并不难（对北大学生甚至可以说是比较简单了）。然而，笔者做出此题花了相当长的时间。笔者也曾将这道题“迫害”给身边同学（都是很厉害的）不下10次，截至目前仅有一人成功做出。究其原因，我认为还是大家对“逆序数”的概念和用法太陌生了。

在高等代数和编程题目上，笔者并没有觉得逆序数有什么用（甚至不会觉得逆序数和高等代数有什么关联），自然不会想到将逆序数作为破题的技巧。考虑到逆序数的证明基本上是这道题最简单的证明，因此，尽管题面和证明高中生也可以看懂，但是没学过逆序数的高中生如果能够独立做出此题，很有可能会重新发现“逆序数的概念”。这可是写入大学教材的成就，对大多数博士生而言也可望不可及啊！

最后，我提出一个我认知范围内的 open question 供看到最后的读者思考：

将  的取值范围改为  ，其中  为整数。此时是否能够通过拓展一般逆序数的定义，构造类似的解？

文 | 马允轩

图 | 周强