解救阿里员工:在下面这个给定条件下,要解救这些厂内员工至少需要多少名厂外用户?

明朝的故事:

明朝,东厂西厂南厂北厂要求每个厂内人员必须有 m 名厂外好友,并且任意两个厂内人员之间的厂外好友重复率不能超过 t,这样就能获得救赎。现在已知大内共有 N 名人员,求解:
要解救这些厂内人员,至少需要多少名厂外人员?




故事背景:

马云强推来往 阿里员工苦不堪言四处拉客

http://it.sohu.com/20131021/n388587293.shtml



推荐  (0) | 28人关注关注
15个答案
37 0

非乌龟代数拓扑硕士,C#程序员

2013-10-22 11:49

——————————10月25日更新————————————
之前已经想到从单纯形单纯复形的角度来考虑这个问题,今天又有了点新想法。

总体想法是,解救阿里员工的问题与单纯复形的构造十分相似。下面来看看如何相似。

拓扑意义上的单纯形就像一维的线段、二维的三角形、三维的四面体等等,而且大小形状可调,只保留“直直”的形状就好了,像这样:

单纯复形呢,简单说就是把这些单纯形像拼积木一样拼起来啦,而且要规则相交,不能是下面这样哦:

得是这种的:

那么它怎么跟原问题联系起来的呢?

(一)n=2
当我们简化假设最大好友重复率为正整数的倒数(1/n),比如n=2时,拿一个一维单纯形也就是线段代表一名阿里员工,线段两端的端点正好可以表示好友的一半,两名阿里员工共用一半好友就是两端线段在一点相交。你看,虽然线段长度可以是任意的,但是,我们要求线段必须是直的,而且是规则相交的,那么两端不同的线段最多只能相交于一个顶点,哇,这跟最多有1/2好友重复恰好对应耶,是不是很神奇?
再来个图表示一下这种有趣的联系吧:

好了,现在我们考虑两万阿里员工加好友,就只需要考虑两万条线段做单纯复形的拼接,最后拼出来的复形的顶点数越少越好(因为一个不同顶点代表1/2要求的好友数,还记得否)。

  • 两条线段只需要在一个顶点处拼起来就好了,这时需要三个不同顶点;
  • 三条线段,拼成三角形最优,这时同样只需要三个顶点;
  • 四条线段,经过并不复杂的尝试,拼成三角形的一点处再加一条线段的形式最优,需要四个顶点;
  • 五条线段,需要四个顶点(自己做个练习?);
  • 六条线段,拼成四面体的一维骨架最优,需要四个顶点;
  • 让我们反过来想,五个顶点已经可以满足一直到十条线段之前的需要了,六条、七条、八条、九条线段都看作十条线段的完全图的一部分就好;
  • ……

嗨,这不就是完全图嘛!所以一般的规律就是阿里员工数小于等于时只需要k+1个顶点,也就是说只需要(k+1)/2份额定好友这么多的不同厂外用户就好了。

(二)n=3
那么重复率等于三分之一,也就是n=3呢?这时阿里员工就变成三角形了,三角形有三条边呀,每条边代表1/3好友数,所以两个三角形最多相交于一条边,也就是重复率小于等于1/3。目标变成了拼接三角形让最后的边数最小。
给个例子,如果有四个阿里员工,那么四个三角形拼成一个四面体,有六条不同的边,则需要三份额定数的不同厂外用户。

(三)任意的n
由以上的推广,任意的n,就是两万个n-1维单纯形拼接单纯复形使得其含有的n-2维单纯形数最小的问题。
而一般的,让我们像n=2的分析最后,反过来想,一个k维单形里包含多少个n-1维单形呢?这是一个纯粹的组合问题,答案是个,因为单形的构造本来就可以由选取若干个顶点张成而得到(回过头研究一下单纯形的构造和定义?)。
所以,阿里员工数只要小于等于,鉴于k维单形的n-2维单纯形数为,而每个n-2维单纯形代表n分之一好友数,那么就只需要这么多份额定好友数的不同厂外用户即可。



——————————10月22日回答————————————
挖坑。待填。

先从具体例子开始考虑。N=2,则为(2-t)x;N=3,若t>=1/2,仍为(2-t)x。这个时候三个员工的好友分布就像一个三角形似的。

所以稍微推广一下,如果我们只研究最大重合率为n分之一的情况,或许可以转化成n维“三角形”“规则”相交的问题。例如n等于二时,三个阿里员工的解决方案就是三条线段围成一个三角形。相交即代表重复。顶点数目即代表厂外用户数。

假若无数阿里员工的线段,排成一张三角形的平面,那么一个人用到两个点,一个点被六个人用,一个人平均只用三分之一个点,而一个点代表二分之一厂外用户,所以平均每人用六分之一厂外用户。这还不是最优,把二维平面的分布扩展到更高维去可以提高点的利用率。
任意图论可以嵌入三维欧式空间,所以研究三维就够了。

一般的n可能就要考虑一个2n+1维空间里的n维单纯形问题了。

不过我很怀疑可以直接查到一个现成的谁谁—谁谁—那谁谁组合数……

36 0

方弦科学松鼠会成员,信息学硕士生

2013-10-24 16:56

首先,分享率t可以用公有好友数目来代替。令,原问题阐述如下:

厂内N人中,每人有m位厂外好友,每两人至多有k位厂外好友,令T(N)为N人共有厂外好友人数,问T(N)至少是多少?

因为问题水很深,我用一下概率方法。

假设N人的厂外好友共有F(N)人,任取两人x,y,它们共有k+1位共同好友的概率是:

这样的一对人是不幸的。我们考虑有多少对不幸的人儿,这个数值的期望。

当期望小于1时,根据概率原则,必定存在至少一个安排,使得没有人是不幸的。于是有不等式(1):


这东西解起来很麻烦,所以我们取近似:F(N)远大于k,并且m和k是常数。于是不等式可以近似为:

于是

是T(N)的一个上界。如果F(N)大于这个东西,那么必定存在符合条件的安排。回代到一开始的近似,这要求N远大于k的(k+1)/2次方。对于现实的数据来说,这个可能不太可能。在这种情况下,还是直接将数据代入不等式(1)然后计算比较方便。


当然,这个界很有可能是不紧的。根据我看到的资料来说,一个确实的下界(但是不知道在那里是否存在符合条件的安排,也就是说这是一个下界)大概是(Ray-Chaudhuri-Wilson Theorem)。而且在概率方法给出的界上,显然有很多安排是满足条件的,也就是说界很可能是不紧的。但是因为这个问题水太深,而概率方法给出的界也很出人意料,所以请容我将就一下……

29 0

已作废->如果t≥1/2
假如4个人,编号A B C D,那么A和B有mt个共同好友;A和C有其他不同的m(1-t)个共同好友,C和D有其他不同的mt个共同好友,B和C有其他不同的m(1-t)个共同好友。这样每个人都有m个好友了,4个人一共占用了2m个好友们。那么4人一组的话最后就需要N/4*2m=Nm/2个好友了。实际上不同的组也可以利用相同的好友。第二组可以选择两个第一组的的mt和两个新的m(1-t)。第三组可以选择两个第一组的m(1-t)和两个新的mt。第四组把第二组和第三组的新好友利用起来。这样就降到Nm/4了。
————————————————————————————

呃,上边的模型太圡了,被废掉了。
简单起见,设t=1/k,考虑k是整数并且m被k整除的情况。
所以以下适用于t≤1/2且m,N比较大的情况。
那么,要求就是,有N个员工。每个人有m个外界好友。任意2个人最多有m/k个共同外界好友。问一共最少要有多少外界好友。
实际上可以画一个N*x的格子。N行表示N个员工。x列里每一列代表m/k个外界好友。每行要选中k个格点,要求是任何两行里同列的格点最多只能有一个。
然后就好办了。p列里选2列,有种方法。我们要的不同选择的数目是N个,所以要求,解得,这种情况下p*N的格子里正好所有“一行填两个的不同填法”都用上了,再在里边多选一个格点一定会有重复。所以其他的格点只能在后边继续添加。
又作废了->这样我们每一行都有2个格点选中了,我们一共要做k/2次。那么一共就是k/2*p*m/k=这么多的外界好友。当然这只是粗略的计算,对于不整除、开方不是整数的情况,会甩出一些尾巴,不过大体上不会有太多出入吧。
不知有没有更好的解法?
//当然啦,t接近1的情况不适用于这个计算,否则k接近1,怎么做k/2次?t较小的话这个结果应该是比较好的吧。t=1的情况当然m个就够用了。有趣的是t比较小的话那个结果是与t无关的,所以除非t小于1/m或接近1,其他情况几乎不受t的影响……
——————————————————————————————————————
呃,上边也作废,失误了。后边不能简单地直接累加,换句话说,在第一次分布做完之后,任何新加的格点都不能有重复的……上边那个其实重复了,所以得到了一个奇怪的反直觉的答案- -
所以在第一组结束之后,后边只能每一行在新的一列里加格点。所以就是直接往后边加正方形对角线……
那么最终结果就是((k-2)*N+p)*m/k这么多的吧。也就是那么多……好吧量级又变回mN了。看来也就这个意思了……

27 0

问题重述:
最少有x名厂外人员,编号为{1,2,3,4,...x}
对于员工i, 如果与厂外人员j是好友,就记为u(i,j)=1,否则不认识就记u(i,j)=0,那么一行u(i,:)中有m个1
所以对于任意两名员工p和q,用u(p)和u(q)对应的位置相乘,再相加,dot production,如果1×1=1,就是说明这两人同时认识一个人,如果1×0,0×1或者0×0,则说明此人不会同时被两人认识。
于是,问题转化为p=u*u'的矩阵中,除了对角线=m以外,其他所有p(i,j)<=m*t
例如:设:
N=4,有4名员工,所以u矩阵有4行;
m=4,每行有4个1;
t=3/4,最多有3名可以重复;
x就是这个u矩阵最小有多少列。
我手算了一个可行解
u=[
1 1 1 1 0 0
0 1 1 1 1 0
1 0 1 1 1 0
0 0 1 1 1 1]
p=u*u'
p=
4 3 3 2
3 4 3 3
3 3 4 3
2 3 3 4
可以看出对角线是=m=4,其他所有格子都<=3。

问题可以重述为:
有一个N*N的矩阵P=U*U',矩阵P中对角线=m,其他所有元素均<=mt。
如果放松一点,可以是N*N的矩阵P=U*U'中对角线=m,其他所有元素均=mt,

嗯,后面我不会解了。

问题重述2:
依据上面的定义,如果已知x,求最大的N。这个好像容易解一些。
所以暴力解了一下:
当m=4, t=3/4的时候:
x=6,N=15
x=7,N=35
x=8,N=70
x=9,N=126
x=10,N=210
也就是说N=C(x,4), x完全不是mN这个量级的。

当m=4, t=2/4的时候:
x=6, N=3
x=7, N=5
x=8, N=14
x=9, N=14
x=10, N=18

当m=4, t=1/4的时候:
x=7~9,N=2
x=10, N=3

很难看的matlab代码:
clear all
close all
m=5;
t=3; % how many same
x=11; % try one by one
u=zeros(1,x);
u(1,1:m)=1;
newu_index=nchoosek(1:x,m);
newu=zeros(size(newu_index,1),x);
for i=1:size(newu_index,1)
newu(i,newu_index(i,:))=1;
end


for i =1:size(newu,1)
if max(u*newu(i,:)')<=t
u(size(u,1)+1,:)=newu(i,:);
end
end
size(u)

暴力算出来的一些结果:

\begin{matrix}
m & mt & N & x
\\ 4 & 1 & 2 & 7
\\ 4 & 1 & 3 & 9
\\ 4 & 1 & 4 & 11
\\ 4 & 1 & 6 & 11
\\ 4 & 1 & 7 & 12
\\ 4 & 1 & 9 & 12
\\ 5 & 1 & 2 & 9
\\ 5 & 1 & 3 & 12
\\ 5 & 1 & 4 & 15
\\ 5 & 1 & 5 & 18
\\ 5 & 1 & 8 & 18
\\ 5 & 1 & 9 & 19
\\ 5 & 1 & 12 & 19
\end{matrix}


18 0

囧呆呆北大信息科学技术学院电子学系教师

2013-10-26 12:11

这里没办法给出简洁的解——这个题难度很大。

实际上这个和通信中,信道编码技术的校验编码(Parity Check Code)问题是完全相同的题:N 个信息比特,M个校验位,每个信息比特必须参与 m 个以上的校验式,而任意两个比特,不得同时参与 t 个以上的校验式。

这算是一个经典命题了吧,不过我还没注意到很经典的解。如果果壳这里有谁给出了漂亮的答案,可以和我联系——我们可以一起写一篇通信方面的论文.... : )

18 0

方程应用数学专业

2013-10-27 18:54

我的拖延症又犯了。拖了这么多天,现在才回复,而且还不是完整版。
我姑且理解问题中的「重复率」是和全体群外好友成正比的数吧。
——————————
我考虑的是,对名组织人员,每个都视为一个 维向量,其中各个坐标分量,都为 0 或 1 ,其代表的意义是——
个向量的第维对应 0 ,就是第名人员不认识第名好友;反之为 1 则认识。所以将是所有的好友的数目。

现在条件限制如下:

  • 不存在坐标全为 0 ,其中 为某个 1 和之间的定值,为从1 到的所有数;也就是
  • 每个向量的坐标都有且恰有 个 1,个 0;也就是
  • 任意两个向量的点乘内积,均不大于 ;也就是

于是问题就变成在给定,与上面的条件限制下,求最小的值。
——————————
挖坑待填……

14 0

ufo5260987423JVM研究者,程序猿管理者

2013-10-24 13:19

对于任意t,Max(Sum)=4*N*m
当t=0,Min(Sum)=4*N*m
当t!=0,Min(Sum)=4*Nm- 6*t*N*m
关于上面的那个式子,可以这样解释:四个厂是四个集合,他们的两两交集的数量为C^2_4……(就是四选2)=6这个情况下我们让这六个交集互相的交集为空,同时令他们元素的数量最大,这就可拿到四个厂所需要的最小人数了吧……
这个问题说白了就是让每个厂子自己独有的人数最少……以上讨论没有讨论一些特殊情况,比如说t>50%javascript:;

13 0

N为偶数时 m*N/2+N*(1-t)*m N为奇数时值域为 [m*(N-1)/2+(N-1)*(1-t)*m ,m*N/2+N*(1-t)*m]

13 0

把厂内分一组a,厂外分一组b,组内关注是无效的。kpi要求必须100个厂外好友。
问题简化:a有2万个点,要求a的每个点的度至少为100,那b的最少点是多少?

答:100啊。。。每个人的好友都是这100,最大2w*100=200万 。厂外的人完全不重复,最多200万的用户。

现在已经500多万了。早超过这个可以接受的数字了。

11 0

冰火梦幻信息与计算科学学士,算法控,AI爱好者

2013-10-25 06:46

阿里这是在学习百度之星还是学习有道难题呢?
熟悉的OJ味儿扑面而来……
我觉得《具体数学》这本书里应该有答案。

基本思路:
1.在最终结果里,每个厂外人员的厂内好友数必定非常接近,理想状态下就是完全相等。
理由:如果两个场外人员的好友数分别是n和n-2,那么前者中任何一个厂内好友都可以脱离前者去和后者交朋友,此时减少了和n-1个人”有重复好友“关系的同时,增加了和”n-3“个人”有重复好友“的关系,无疑有助于降低重复率。

2.在最终结果里,每两个厂内人员都有恰好floor(m * t)个共同好友。
证明有点麻烦……

3.从1个厂内人员的情况开始,逐渐增加厂内人员,寻找需要厂外人员数的规律。

0 0

yangyanggoods私立樱才学园学生会入会积极分子

2013-10-22 03:08

假设有mt个好友是所有人共有的,剩下全是私有好友,则需要 (1-t)Nm + mt 个。虽然这个貌似不是最优解……

0 0

难怪我们这些做淘宝云客服的成了香饽饽,好多厂内员工加好友哇。

0 2

Ralph临床医学学士

2013-10-23 00:22

我觉得,在回答这个问题之前,首先应该温习一下关于SNS的“六度分隔理论”:
http://kb.cnblogs.com/page/64039/

0 0

YY在这里冒充强力围观者 伪不吐槽会死星人 后期类社稷狮

2013-10-24 10:58

作为一个厂外人士已经有1594个好友了。真正认识的人只有二十多个。

0 0

grylls你看起来好像很好吃

2013-10-25 09:07

有这么一条河,河里有很多鱼要吃JJ,问如何让一个全是男人的队伍通过这条河。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区