看到标题你或许会内心一惊，但是请放心，这里是正经博客，讨论的是一个数学问题

序

小便池问题是在我初中时期广为流传的一个问题(梗)。 在和H君和R君(当然，我早就和悦悦讲过🙂)两次提起这个问题之后，终于勾起了我重新解题的冲动。 距离上一次思考这个问题已经是十多年前了，彼时的我并没有得出通解，一觉过后也就未再深究。 今天希望我可以顺利解出。

背景

男同胞可以选择跳过本节

一般男厕所由两部分组成，即小便池和单间。

其中小便池通常一字排开，条件好一点的还会有隔板隔开。

然而，小便池资源在很多时候不能被充分利用。对于不能明白其中缘由的朋友，请看下图。

图中蓝衣选手正处在一个尴尬的境地，中间空闲的小便池并不被他视为有效资源。

这在医学上其实是一种病症，尿羞症，学名“境遇性排尿障碍”。 当有他人在侧时，无法正常解决生理问题。病情严重的，甚至有人在门外等待都会造成障碍。

不负责任的说，大多数男生都有这一症状，区别只是轻重。

当然，严重的病情我们留由医生去解决。今天的"小便池问题"要解决的就是蓝衣选手的困境。

问题

对于任意男生，在面对一字排开的小便池时，其选择位置总是遵循以下“公理”

1. 选择离门最近的位置
2. 如果已经有人，则选择离所有人最远的位置，当有多个位置的时候遵循规则1
3. 永远不和别人相邻

现有$n$个男生，求所需小便池数量$U(n)$。

另有逆问题，若有$n$个小便池，最多容纳男生的数量$P(n), P=U^{-1}$。

解题

拿到问题，首先我们可以推演前几项，看看有什么规律。(我们用$X$来标记有人的位置，用$O$来标记空位)

然而到了4个人的时候，情况有些不一样。天真的同学会脱口而出答案是7。 然而如果只有7个小便池，会发生下面的窘境。

是的，第3个男生遵循公理2，直接站到了正中心。 这使得第4个男生无路可走了。

所以4个男生的情况，需要8个小便池，即$XOOXOXOX$

下面提供了一个小组件可以进行简单实验。

通过实验，我们得到了更多的几项

当然，我们不能永远实验下去，我们需要对现有的结果进行归纳总结和推理计算。

通过对现有结果的观察和公理3的理解

• 最差情况下每个男生占用3个位置，头尾除外
• 最好情况下，所有男生间隔站开

即

另一方面，由于头尾总是会被先占用，又由于公理3，第2个和倒数第2个位置总是不可用。 我们可以摘头去尾后另计$P'(n)$，其表示在首尾有人的情况下，中间n个空位可以容纳的人数，易知：

每当新人加入时，原有区域就被划分为两块，而每一块都可以看作时一个独立的$P'$问题，即：

带入$P(n)$替换可得：

然而，到这里，我陷入了僵局。仔细观察思考，发现了一些规律，但是未能找出通项。

这里需要特别感谢徐缘博士，给我提供了一些突破性的提示。

注意观察函数图像：

容易发现：

• 在$(2^n, 2^n + 2^{n+1} + 1]$区间，斜率为0
• 在$(2^n + 2^{n+1} + 1,2^{n+1}]$区间，斜率为1

这也就得到了最终的答案：

从现实意义上来说

• 小便池的境况在每个$[2^n, 2^{n+1}]$的前半区间逐渐尴尬，每个人趋于占用3个位置 (不过反过来看，由于间隔变大，每个男生的症状都得以缓解)
• 而在后半区间，尴尬逐渐化解，最后得到每个人之间只间隔一个位置，即每个人占用2个位置 (资源的尴尬得以缓解，而病人的尴尬逐渐增大)

这一题解可以说非常符合直觉，也非常符合美学。

结语

关于这道题目的解答就到这里了，过程并不似想象中那样简单。

在准备做这道题的之前，我还发现了一篇类似的论文，发表于2010年。 但是该文章的重点是小便池的决策问题，即如何才能避免被靠近。 属于同一个领域的不同问题。链接已附在文末。

另一方面，这道题也很适合作为计算机算法的试题。 乍一看很容易以为可以用一个简单的递归来解，仔细一想又不是那么一回事。 如果一路思考下去，就可以从$O(n^2)$进步到$O(log(n))$，再进一步解通项可以改进到$O(1)$。 可以同时考察编程能力进而考察数学能力。

当然，本文的小便池模型直接拿来面试似乎有些不妥。

顺便在此征集一下，有没有类似的模型场景可以替换掉“小便池”，欢迎评论！

参考

• The Urinal Problem, Evangelos kranakis and Danny krizanc
• 男生尿尿尴尬问题研究报告