The Urinal Problem 小便池问题
2021-09-08
数学
趣谈
👋 ‍️‍️阅读
❤️ 喜欢
💬 评论

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

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

背景

男同胞可以选择跳过本节

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

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

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

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

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

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

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

问题

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

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

现有nn个男生,求所需小便池数量U(n)U(n)

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

解题

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

U(1)=1,XU(2)=3,XOXU(3)=5,XOXOX\begin{aligned} U(1)&=1, X\\ U(2)&=3, XOX\\ U(3)&=5, XOXOX \end{aligned}

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

XOOXOOXXOOXOOX

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

所以4个男生的情况,需要8个小便池,即XOOXOXOXXOOXOXOX

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

池数:人数:0
O

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

U(4)=8,XOOXOXOXU(5)=9,XOXOXOXOXU(6)=14,XOOXOOXOOXOOX\begin{aligned} U(4)&=8, XOOXOXOX\\ U(5)&=9, XOXOXOXOX\\ U(6)&=14, XOOXOOXOOXOOX \end{aligned}

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

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

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

3n2>=U(n)>=2n13n - 2 >= U(n) >= 2n - 1

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

P(n)=P(n+4)2P(1)=1P(4)=2P(5)=3P(10)=4\begin{aligned} P'(n) &= P(n+4) - 2 \\ P'(1) &= 1 \\ P'(4) &= 2 \\ P'(5) &= 3 \\ P'(10) &= 4 \end{aligned}

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

P(n)={2P(k1)+1,n=2k+1P(k2)+P(k1)+1,n=2k\begin{aligned} P'(n) = \begin{cases} 2P'(k-1) + 1&, \quad n = 2k + 1 \\ P'(k-2) + P'(k-1) + 1&, \quad n = 2k \end{cases} \end{aligned}

带入P(n)P(n)替换可得:

P(n)={2P(k+1)1,n=2k+1P(k)+P(k+1)1,n=2kP(1)=P(2)=1P(3)=P(4)=2\begin{aligned} P(n) &= \begin{cases} 2P(k+1) - 1&, \quad n = 2k + 1 \\ P(k) + P(k+1) - 1&, \quad n = 2k \end{cases} \\ P(1) &= P(2) = 1 \\ P(3) &= P(4) = 2 \end{aligned}

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

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

注意观察函数图像:

容易发现:

P(2n)=2n1P(2^n)=2^{n-1}
  • (2n,2n+2n+1+1](2^n, 2^n + 2^{n+1} + 1]区间,斜率为0
  • (2n+2n+1+1,2n+1](2^n + 2^{n+1} + 1,2^{n+1}]区间,斜率为1

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

P(2k+t)={2k1+1,0<t<=2k1+1t,2k1+1<t<=2kP(1)=1\begin{aligned} P(2^k + t) &= \begin{cases} 2^{k-1}+1&, \quad 0<t <= 2^{k-1}+1 \\ t&, \quad 2^{k-1}+1<t<=2^k \end{cases} \\ P(1) &= 1 \end{aligned}

从现实意义上来说

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

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

结语

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

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

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

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

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

参考


Copyright © 2020-2022 Dean Xu. All Rights reserved.