娱乐 奇怪的算法挑战【第③期】池塘的鸭子

[Muriya Tensei]

好久没来水贴了，最近看到了一个有意思的题目，甚至难倒了好几个大佬，来分享一下

（根本就不是算法题嘛，简单的概率题）

有一圆形池塘，在池塘中被遗留了n只小鸭子，小鸭子们等概率均匀分布在池塘中。

那么请问这n只鸭子们全部位于同一个半圆的概率是多少呢？

 

tip: 不妨想一想两只鸭子的情况

easy: n=2

mid: n=3, n=4

hard: n∈N+

ex: 除了半圆，即1/2圆的情况外，有没有办法考虑1/m圆的情况呢（m为正整数）

ex2: 有没有办法考虑1/m圆的情况呢（m为大于一的正实数）（m可能会∈(1,2)）

十一月 1, 2022，由Muriya Tensei修改

[Muriya Tensei]

于 2022/10/28 于 AM6点12分，jake147127说道:

对不起，是我太自大了，我不应该觉得自己可能可以，我不配

想了好几个思路，最后唯一可能有用的还是最开始那个，然后又不会算概率

 

吃瓜等大佬解题，然后我现在就预言一波，我瞎吉儿写的这一堆全部都不会用上

  显示隐藏内容

在n>=3的情况下概率为P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2)，Y1,Y2,...,Yn独立同分布随机变量，Yi~Uniform(0,1)，至于怎么算，我不知道

要怎么算我不知道，能不能算我不知道，思路是否合理我也不知道，但我不配这件事是十分清楚的

 

语法稀烂见谅，如果读起来很难受...可以尝试忍着，因为我也没有办法

用线段连接每只鸭子和圆心，当存在一个至少180度的角时，可画一条通过圆心的直线将所有鸭子分到一个半圆；同时，不存在至少180度的角时，无论怎么分配半圆，两个半圆都会各自包括至少一条线段，也就是说不能将鸭子分配到一个半圆；因此，至少180度的角的存在性与鸭子全部在同一个半圆等效

现在就要找存在至少180度的角的概率。设n=鸭子数量

n=1：唯一的角是360度

n=2：两个角相加为360度，因此各自最小为180度，所以任何配置都在同一个半圆中

n∈N+ 且 n>=3：

前两只鸭子放下后，取大于180度的那个角，作角平分线，设该条线为角度0，逆时针旋转时角度增加，角度范围为[0,360)

设随机变量X1,X2,...,Xn为每只鸭子的角度，即Xi~Uniform(0,360) ∀i∈[n]，且{X1,X2,...,Xn}为独立随机变量

注意max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180⇔所有鸭子在同一个半圆中

证明：

1. max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180⇒所有鸭子在同一个半圆中：

随便画一个包含角度max{X1,X2,...,Xn}和角度min{X1,X2,...,Xn}的半圆就包括了所有鸭子

2. 所有鸭子在同一个半圆中⇒max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180：证明其逆否命题比较容易，即：

max{X1,X2,...,Xn}-min{X1,X2,...,Xn}>180⇒没有任何包含所有鸭子的半圆：

当max{X1,X2,...,Xn}-min{X1,X2,...,Xn}>180时，将所有半圆分为两类考虑：

第一类：包含角度0的半圆；这种半圆要么不包括角度X1，要么不包括角度X2

第二类：不包含角度0的半圆，由于max{X1,X2,...,Xn}-min{X1,X2,...,Xn}>180，不可能同时包含最大值和最小值

 

尝试计算P(max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180)

设f:[0,360)->[0,1) f(x):=x/360

定义随机变量Y1,Y2,...,Yn，Yi:=f(Xi)~Uniform(0,1)

可以证明P(max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180)=P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2)

 

现在计算P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2)：

不会算

 

淦，反正做不出来，不如搞搞事：

  隐藏内容

一共有n只鸭子，对应n个一样的球，放入2p个贴着标签{1,2,...,2p}的箱子内，p是个很大的正整数

猜测是P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2)可能可以这么计算：

将n个球以任意方式放入2p个箱子中，设M:=放有至少一个球的箱子中，标签最大的；m:=放有至少一个球的箱子中，标签最小的

所有的排列组合中，M-n<p的组合数量除以全部组合的数量，可能会很接近上述概率

如果能找到合适的式子求p->∞的极限的话，或许这堆箱子的性质就跟实数区间的性质很接近了...？或许往箱子里放球的行为就和生成均匀分布随机数一样了...？

 

以上纯属瞎猜，直接按以上思路继续瞎写

 

首先要找到M-n<p的组合数量

设m:=1,2,3,...,p+1，m为放有至少一个球的箱子中，标签最小的：

将一个球放置在箱子m中，剩下的n-1个球以任意方式分配在m,m+1,...,m+p-1共p个箱子中，每个m有(n+p-2)C(n-1)种组合方式

设m:=p+2,p+3,...,2p：

将一个球放置在箱子m中，剩下的n-1个球以任意方式分配在m,m+1,...,2p共(2p-m+1)个箱子中，每个m有(2p+n-1-m)C(n-1)种组合方式

一共有(p+1)( (n+p-2)C(n-1) ) + (2p+n-1-(p+2))C(n-1) + (2p+n-1-(p+3))C(n-1) + ... + (2p+n-1-(2p))C(n-1)种组合方式

等于(p+1)( (n+p-2)C(n-1) ) + (p+n-2)C(n)

 

全部的组合方式有(n+2p-1)C(n)种

 

要算的概率应该是[(p+1)( (n+p-2)C(n-1) ) + (p+n-2)C(n)] / (n+2p-1)C(n) = (np+n+p-1)*(n+p-2)!*(2p-1)!/(p-1)!/(n+2p-1)!

然后经过一些乱七八糟的可信性非常可疑的极限运算...得出p->∞时，上述表达式->(n+1)*(1/2)^n

代入n=3，得1/2，应为3/4，不出意料是错的，好耶

 

啊，我究竟是写了些什么鬼东西

仔细看了下你的表达式。试图想出你是怎么化简的（无果）。但是结果吧，令n=n-1就对了好像（偏移了一个）

想了想这个假设。原题设是一个环的话，展成线应该会偏小吧，概率上会差多少呢（难道是(n+1)/2n）大胆猜测小心求证（

十月 29, 2022，由Muriya Tensei修改

[Muriya Tensei]

于 2022/10/29 于 PM5点42分，jake147127说道:

“大胆猜测小心求证”，后半段其实我已经纯粹是整活的心态了，大佬你不用这么温柔的

某种意义上还可能对了可还行

  显示隐藏内容

草（日语），突然看懂了上面fangaa说的方法，好像用那个方法算出来正好是令n=n-1

思路是个好东西，可惜我没有

哎呀，忘了谢谢大佬给的题，虽然做不出来但还是很有意思的比追赶落后的课程进度有意思多了

还有就是，写的乱七八糟的也在认真读非常感谢

 

关于环展开成线的部分...

  显示隐藏内容

好像确实是这样的。

重新想了一下，按我第一段证明的做法，线段是根据角平分线的位置生成的，根据前两只鸭子的位置不同会生成不同的线段。但是，事件max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180的样本空间只是在这一条线段上随机扔n只鸭子，而“所有鸭子在同一个半圆中”的样本空间是在那个圆上随机扔n只鸭子，而这个生成的线段确实是不与圆等效的

换一种方法说，就是在生成的线段上的每一组随机数，圆上面都找到对应的一组随机鸭子，形成满射；但是反过来不行，圆上面只要是经过旋转后相同的随机鸭子组合，对应的都是同一组生成的线段上的随机数

 

对于之前概率的重新思考：

  显示隐藏内容

那么不如一开始就固定圆一个角度为0，画一条线段，然后开始往里随机扔鸭子，这样的话两个样本空间就确实有双射了

这样的话，所有鸭子在同一个半圆中的事件与线段上的什么事件等效呢？

首先是max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180这个事件；但还要考虑所有鸭子在线段两边，如果将线段两头连接起来会在180距离之内的情况，不过这种情况其实就是线段中有个距离至少180的区间完全没有鸭子的事件，但这个事件与max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180这个事件有双射，下面证明：

上述的max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180这个事件先叫做事件A，后者叫事件B吧

每个事件A中的随机变量，先加180再取模360，会形成一个距离至少180的没有鸭子的区间；反过来，每个事件B中的随机变量，若小于180就加180，否则减180，就得到了一组事件A中的随机变量

也就是说，这两个事件的概率是相等的！（大概，吧；离散情况下有双射应该是这样的，连续情况下没学过，瞎猜的）

那么，只要算出P(max{X1,X2,...,Xn}-min{X1,X2,...,Xn}<=180)再乘以2就可以了！大概.........

 

但这样的话之前算出来的(n+1)*(1/2)^n肯定有问题...在此之上再乘以二，n=3时概率算出来变成1了，呃...

但是等等！之前说的排列组合的解决方式，经过稍微修改后，只论结果的话，确实能得到正确答案：

 

修改后的排列组合：

  显示隐藏内容

一共有n只鸭子，对应n个一样的球，放入2p个贴着标签{1,2,...,2p}的箱子内，p是个很大的正整数，箱子放成一个圆圈的形状，就是说箱子1和箱子2p是邻接着的

猜测是鸭子在某个半圆内的概率可能可以这么计算：

将n个球以任意方式放入2p个箱子中，其中如果所有的球都在某组连续的p个箱子内的话，就对应着所有鸭子都在某个半圆

然后这个情况下找到“所有的球都在某组连续的p个箱子内”除以所有排列组合的比例，在此基础上求p->∞的极限，使该离散的排列组合问题不断接近连续的池塘鸭子问题，或许...？

 

以上仍然纯属瞎猜，直接按以上思路继续瞎写

 

设m:=1,2,3,...,2p：

将一个球放置在箱子m中，剩下的n-1个球以任意方式分配在m,m+1,...,m+p-1共p个箱子中（如果数值超过2p，取模2p），每个m有(n+p-2)C(n-1)种组合方式

一共有(2p)( (n+p-2)C(n-1) )种组合方式

（看了一下楼下说的李永乐老师，这里似乎和李永乐老师“鸭王”的说法有相似之处，是选定了第一个球（对应鸭王）的位置，然后将剩下所有球分配在之后p个箱子（对应半圆））

 

全部的组合方式有(n+2p-1)C(n)种

 

要算的概率应该是(2p)( (n+p-2)C(n-1) ) / (n+2p-1)C(n)，具体计算见附图：

得到结果n*(1/2)^(n-1)

 

虽然没有什么头绪证明这个答案与连续性的鸭子池塘问题之间的联系，但单论答案，貌似是对的（

 

追加：

  隐藏内容

话说，这样一来，如果这层上面算的概率没错的话，

定义独立随机变量Y1,Y2,...,Yn~Uniform(0,1)，n>=3

P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2) = n*(1/2)^(n-1) / 2 = n*(1/2)^n

等于找到了个P(max{Y1,Y2,...,Yn}-min{Y1,Y2,...,Yn}<=1/2)的表达式...

 

话说不会大家都知道李永乐老师，只有我一个在这里傻傻做题吧

坏了，原来李永乐老师讲过这个题了

这个题当初我也证明了好久。

我采用的个办法是，对于每个鸭子的分布可以看其关于圆心对称（或者说是旋转180°）的位置

那么本身n只鸭子就有了2n组点。简单分析一下就能知道，只有相邻的n组点可以被同一个半圆（180°）包括，而这组点的选取方法共有2n种。

概率就是 2n/2^n 即n/2^(n-1)  

因此不光是半圆（180°）的情况，也可以这样映射（只是非整数的情况不确定对不对，感觉应该也是对的）就可以得到 n/m^(n-1) 这个式子

十一月 1, 2022，由Muriya Tensei修改

[Muriya Tensei]

于 2022/10/29 于 PM7点07分，抹消思绪说道:

小朋友们大家好你是李永乐老师？

惊了，李永乐老师居然讲过这个题了。应该是10/18在ACM群里看到了转发的NGA帖子提到这个（4只鸭子的）题。然后简单延拓一下得到这个问题