博苏克-乌拉姆定理解项链珠宝分配问题

  |  

珠宝分配问题可类推到计算机中内存分配的优化,主要介绍一下证明思想。

项链珠宝分配问题

你和你的1个同伙偷了一串长度为n的项链,它上面有m种颜色的珠子,我们假设项链为链状的,并且每一颗珠子都是随机分布,现在我想知道,对于给定的n,m你在最坏情况下最少需要切多少刀 才能使得你们可以通过每人获得一些切完之后的项链,并且满足每个人得到的每种宝石的数量刚好相同,我们假设珠子的数目一定是偶数。

例如,现在有下面这一串项链

将其切四刀后

上面的一段分给甲,下面的一段分给乙,可以看到甲乙分到的宝石对应种类的数量各是一样的,比如,甲分到四个蓝宝石,乙也分到四个蓝宝石。

该问题属于离散数学范畴

博苏克-乌拉姆定理

博苏克-乌拉姆定理是关于有限维空间中的连续奇映射的著名定理。

设X和Y是有限维赋范线性空间,且dim Y<dim X,S为X中的单位球面,f:S→Y为连续奇映射(f(-x)=-f(x),∀x∈S),则存在x∈S使f(x)=0。 [3]

博苏克-乌拉姆定理表明,任何一个从n维球面到欧几里得n维空间的连续函数,都一定把某一对对蹠点映射到同一个点。

例如空间中有一个球面

将其以某种规则映射到平面上(并不一定是垂直映射,可以是一种复杂的扭曲形式)

而你总能在球面上找到两个完全处于两极的点

经过映射后重合为一个点

该定理是拓扑学中的重要定理

如果将地球看作一个理想的球面,则根据该定理,地球上必有两个相对两极位置的点,其气温与压强完全相同。

利用拓扑学解决离散数学问题

我们首先要做的,是将宝石分配化为连续分布

例如将两种宝石的情况看作这样

令其总长度为1

接着切两刀

分成a,b,ca,b,c三段,a+b+c=1a+b+c=1


现在回忆一下标准球体的方程:

x2+y2+z2=1x^2+y^2+z^2=1

于是我们可以将a,b,ca,b,cx2,y2,z2x^2,y^2,z^2对应起来。

现在我们做一个约定x,y,zx,y,z中,正的解表示分配给小偷一号,负的解表示分配给小偷二号

比如x=ax=\sqrt a就是a段分配给小偷一号,x=bx=-\sqrt b就是b段分配给小偷二号

可以表示成这样


我们发现,x,y,zx,y,z的取值,可以表示为一组分配方案,这就将一个离散的分配问题与空间的几何连续问题相关联了起来!


我们现在设定一个函数f(x,y,z)f(x,y,z),这个函数的输出结果为该小偷分得的不同种类宝石的数量

可以知道,f(x,y,z)f(x,y,z)f(x,y,z)f(-x,-y,-z)实际上表示的是同一种分配方式

并且,f(x,y,z)f(x,y,z)的输出结果,我们在两种宝石的情况下设其为g(m,n)g(m,n),其意义就是三维到二维坐标的映射!


于是,根据博苏克-乌拉姆定理,必有一对球面上的对蹠点,经映射后两点重合

也就是必有这么一组分配方案,能满足两个小偷各自得到的宝石各种类的数量,即使对称交换分配后,仍然相等,即公平均分。

结论

对于m种宝石的项链,至少可以用m刀平均分配,并且可以用m+1维的球面(超几何球面)结合苏克-乌拉姆定理证明。

视频讲解


附个笑话

俩小偷偷了17种珠宝的项链。

一个说:“哟,咱们挨个数数珠子, 平分如何?我可以用18维超球体证明只要17刀就可以平分完。”

另一个:“用不着,一刀就够了。“

“哪一刀?”

“我给你一刀”

文章目录
  1. 项链珠宝分配问题
  2. 博苏克-乌拉姆定理
  3. 利用拓扑学解决离散数学问题
    1. 我们首先要做的,是将宝石分配化为连续分布
  • 结论
    1. 附个笑话
  • 本站总访问量 | 本页面被访问 | 本站访客数
    载入天数...载入时分秒...