|
这道题是我一哥们儿博士论文中的问题。他说很难，问了几个数学教授都不知怎么解。这儿有不少厉害的人，我就不辞辛苦把问题简化一下贴在这儿，看看谁会解。
有N个人和N个房子。我们要把这N个房子分给这N个人。这N个人每人对N个房子根据自己的喜好有一个排序（如第i个人：（hi1,hi2,...,hiN)。hi1表示第i个人最喜欢的房子，hi2是这个人第二喜欢的房子，以此类推。）现在有两种公平（对每人都一视同仁）的分法：
1。将这N个人排序，共有N!种。以1/N!的概率随机取一个序列。然后让排在第一的人根据他的喜好的排序选他最喜欢的房子，排在第二的人选剩下(N-1)房子中他最喜欢的，依此类推。大家知道这样最后会得到一个随机的分配，我们用一个(NxN)的矩阵代表最后的分配。这个矩阵行代表人，列代表房子，矩阵的第(k,j)项表示第k个人得到第j个房子的概率。矩阵每一列和每一行的和都是1，代表每个房子只分给一人，每人只得1个房子。大家可以用4个人4个房子的情况做个例子，（假设每人的喜好都是一样的，房子1，h1,最好，房子4，h4,最差，（h1,h2,h3,h4）),用这种分法，最后得到的是一个所有项都是1/4的4x4的矩阵，即每人都以相同概率得到每个房子。这样分也很公平。下面是第二种分法，有点复杂。
2。第一步：将N个房子分成m份(partition into m components，m是1到N的任意自然数),假设这样的partition是任意的。然后随机选出m个人(每人以相同概率被选中)，把这m份房子一人一份分给他们。然后这m个人每人指向有自己最喜欢的房子的拥有者， 这样的指法造成至少一个循环(cycle)（大家可以证明，这m个人每指一次，就存在至少一个cycle。注意，这m个人的每人可以指向自己，表示自己分到的一份中有自己最喜欢的房子。第一次没有分到房子的人，没有人会指向他们。我听说这其实是一种很有名的算法。）让这个
循环(cycle)中的人交换后每人得到自己最喜欢的房子(比如，第i个人指向第j人，第j个人指向第k个人，第k个人又指向第i个人，则(i,j,k)形成一个cycle。我们让第i个人从第j个人分到的一批房子中拿到他最喜欢的，j则从k那儿拿到他的，而k从i那儿得到k最喜欢的。因为是一个cycle,所以feasible...)。
第二步：将第一步中形成循环(cycle)的人及他们所拿到的房子分出去。还剩下(N-k)个人和房子。假设第一步循环cycle中有k个人，(i1,i2,i3,...,ik)。拿走这k个人和k个房子后，会有一些房子（这k个人原先第一步每人分到一批房子，但经过cycle后，每人只能拿一个房子走）剩下来。（注意，原先m个人还剩下(m-k)个第一步分到房子的人，这些人还拥有第一步分到的房子，这些房子不动，还是暂时在这(m-k)个人手上）。把这些k个人剩下的房子以相同的概率分给剩下的(N-k)个人（即分给还没最终拿到房子的人）。然后，手头上暂时有分到房子的人（<=(N-k)）再指向暂时拥有自己剩下(N-k)个房子中最喜欢的房子的人。这样又会形成至少一个循环cycle。这样第二步又会分出去一些拿到自己最终分配的人。依此类推，我们会在有限步中使每人拿到一个房子，达到最终分配。
大家可以看到，从第一步看，每人是被相同对待的，所以，2。也是一种公平的分法。2。有些复杂，我们还用前面那个4个人的例子。每人都给4个房子有相同的排序。假设第一步房子的partition是(h1,h2)U(h3,h4),即房子1和房子2在一起，房子3，4在一起。从4人中随机选2人出来，把(h1,h2)分给第一人，(h3,h4)分给第二人，这二人会形成一个cycle。因每人都喜欢房子h1,故第一步中只有一人拿到最终分配，h1(第一人指向自己)。我们把这个人和房子h1分出去。现在房子h2被剩下来了。h2以相同概率随机分给剩下的3个人，然后剩下的（被暂时分到房子的）人又指向有自己最喜欢房子的人（每人都指向分到h2的人，因为h2是除了h1之外大家最喜欢的），这样第二步分到房子h2的人指向自己，他可以拿到h2作为自己的最终分配。这样还剩下两个人，其中又一人最初分到(h3,h4)（注意，他还暂时拥有这两个房子），他虽然比较lucky,但前两次他都指向又h1和h2的人，没人指向他，所以他还没走。现在他最好的选择是指向自己，拿到h3。最后剩下一人拿到h4。大家可以算算，最终的分配矩阵是一个4x4的每一项都是1/4的矩阵，和第一步一样。（其实这个矩阵和第一步的partition无关，若partition是(h1)U(h2,h3,h4),分配结果相同。）
ok,这个组合概率的问题是:证明对所有的N,所有的N个人的喜好排序，第一种分法和第二种分法得到的分配矩阵是相同的（第二种分法中的partition也可以是任意的）。
|
