非传递性骰子:一个模型及猜想

请看下面三枚骰子,它们有什么特别的地方?

D1: [1,4,4,4,7,7]
D2: [2,5,5,5,5,5]
D3: [3,3,3,6,6,6]

初看起来,除了每面的点数有点奇怪,貌似也没别的特别之处。

如果有人跟你打赌,大家从这三枚骰子中各选一颗,然后看谁掷出的点数比较大,那么,最好的策略是什么呢?通过简单的计算,我们知道,D2战胜D1的概率是7/12,D3战胜D2的概率是7/12。算到这里,有人可能会说,既然D2比D1强,D3比D2强,那么最好的策略当然是选D3了。

然而,计算一下D1和D3的胜负概率,我们发现D1战胜D3的概率也是7/12!也就是说,D2比D1强,D3比D2强,但是反过来D1竟然比D3强!用数学的术语来说,就是“A战胜B的概率大于1/2”这个关系在{D1,D2,D3}这个集合中不是传递的。这就是“非传递性骰子”这个名字的来历。

我个人对非传递性骰子则有另一个叫法:古惑骰。广东那边把出千或者作弊之类的行为统称“出古惑”,而一套非传递性骰子正是出古惑的好帮手。你只要出示这套骰子,跟对手赌一人挑一枚谁掷出的点数比较大,然后再“谦让”一下让对手先选。一般来说思维稍微简单的人,或者说不太习惯算概率的人,都会中招的。股神巴菲特就曾经尝试在他的一位朋友上出这招,可惜没有成功,因为这位朋友是比尔盖茨,大概是看着巴菲特的样子知道他不安好心,一算概率发现果然是一套古惑骰……

如果想拿古惑骰赚外快的话,有个问题是绕不过的:一套古惑骰如果有n枚,每枚有s面,那么最大的确保获胜概率p是多少呢?也就是说,如果我们想确保,无论对手挑了哪一枚骰子,我们都能挑出另一枚,使得我们获胜的概率至少是p,那么p的最大值是多少呢?这个概率p就代表了我们获胜的概率,所以当然是希望越大越好。

记一套n枚s面的非传递性骰子为D={D_1, D_2, …, D_n},每个D_i都是长度为s的列表,代表着第i枚骰子每一面的值。我们将这种表示法称为面值表示。我们记D这套骰子的确保获胜概率为p(D)。现在我们要研究的问题,就是最大化p(D)。

一个数学模型

我们知道,骰子投掷之间的胜负跟掷出的值的次序有关系,但与具体的值没有关系。所以我们可以假定骰子每一面的值都是自然数。同理,平局是不会增加获胜概率的,所以我们假定每一颗骰子每一面的值都不一样。这样的话,我们可以将D看成对从1到n*s的正整数的一个划分,每一个D_i都是{1..n*s}的一个s元子集。

为了最大化p(D),我们要分析使p(D)最大化的D的结构。我们记骰子D_i负于D_j的概率为p(D_i,D_j)。

构造有向图G=(V={P_1, …, P_n},E),对于固定D_i,取D_j为对上D_i胜率最高的骰子(如果有多枚的话任取一枚),那么在G中添上从P_j指向P_i的有向弧,并在弧上标上p(D_i,D_j)。容易知道,G有n个顶点和n条有向弧,所以必然存在至少一个环。我们将某个环的确保获胜概率定义为环中弧上标上的概率的最小值,显然这与p(D)的定义是协调的,也就是说p(D)正是G中弧上标上的概率的最小值。

我们有如下的引理:

引理一:如果D是一套非传递性骰子,则存在另一套同样规格的非传递性骰子D’,使得p(D)<=p(D’),并且D’对应的有向图G’是一个由n个顶点组成的环。

我们暂且承认这条引理。证明将在稍后给出。故此我们可以假定D_2胜D_1,D_3胜D_2,等等,一直到D_1胜D_n,并且不考虑其它骰子对的胜负概率。

一套非传递性骰子D又可以看成是对集合{1..n*s}的一个染色d: {1..n*s} -> {1..n},其中满足{1..n}的每一个元素都有s个原像。我们将d这种对非传递性骰子的表示称为染色表示。通过对于任意D_i中的任意元素x规定d(x)=i,我们容易看出这种对应关系。Par abus de notation(这句话不好翻译,大概就是“我们来随便扩展定义吧”的意思),我们记p(d)为d所代表的非传递性骰子D的确保获胜概率p(D)。

在承认引理一的前提下,我们来看看对d进行扰动会有什么结果。对于{1..n*s-1}中的任意元素x,考虑如下构造的染色d_x:对于y不等于x或者x+1,令d_x(y)=d(y);定义d_x(x)=d(x+1), d_x(x+1)=d(x)。显然,d_x就是将d中的x和x+1的染色交换。

现在我们来考虑p(d_x)。如果d(x)=d(x+1)的话,显然p(d_x)=p(d)。如果d(x)=d(x+1)+1 mod n,也就是说x+1所在的骰子负于x所在的骰子的话,显然p(d_x)>=p(d),因为交换后两颗骰子之间的胜率提高了。如果d(x)+1=d(x+1) mod n的话,同理p(d_x)<=p(d)。在其它的情况下,因为交换的值属于两枚没什么关系的骰子,所以有p(d_x)=p(d)。

根据上面的观察,我们有如下的引理:

引理二:如果d是一套非传递性骰子D的染色表示,那么存在另一套非传递性骰子D’,满足p(D’)>=p(D),并且它的染色表示d’满足如下条件:数列(d'(1), d'(2), …, d'(n*s))的形式为1^m_1, 2^m_2, …, n^m_n, 1^m_{n+1}, 2^m_{n+2}, …(其中i^j表示将i重复j次),并且对于任意k,如果m_k=0,则m_{k+1}=0。同样,数列m也可以表示一套非传递性骰子,我们将m这种表示称为区块表示。我们同样用p(m)表示m代表的非传递性骰子D的确保获胜概率p(D)。

证明:令d’=d,然后执行下列算法:对于所有d'(x)+1<>d'(x+1) mod n,如果d'(x)>d'(x+1),则用d’_x取代d’。算法必然停止,因为每次交换都会使逆序数降低。最后得到的就是d’。根据算法可知d’有结构(不失一般性设d'(1)=1):

1^m_1, 2^m_2, …, n^m_n, 1^m_{n+1}, 2^m_{n+2}, …,其中m_i是自然数,m_1>0。

容易知道,骰子D_i被战胜的概率是p(D_i,D_{i+1 mod n}) = m_i*m_{i+1}+(m_i+m_{i+n})*m_{i+1+n}+…。若m_k=0,将m_{k+1}换成0,将m_{k-n+1}换成m_{k-n+1}+m_{k+1},这样得到的m’也是一个合法的区块表示,并且容易验证p(m)<=p(m’)。将m_{k-1}换成0,将m_{k+n-1}换成m_{k+n-1}+m_{k-1}也有同样的效果。通过这两种变换,我们可以调整使得d’对应的m’中所有非零的m_i都是连续出现的,这正是需要证明的,证毕。

m是一个合法的区块表示当且仅当对于所有k属于{1..n},sum_i(m_{k+ni})=s。从数学模型的角度来说,因为非0的m_i是连续出现的,所以最多只需要m的n*s项就可以了。

现在我们来证明引理一。

引理一的证明:取{D1, D2}的区块表示(a_1, b_1, a_2, b_2, …, a_s, b_s)。对于这样的区块表示,我们定义p((a_i),(b_i))=p(D1,D2)。容易知道:

p((a_i),(b_i)) = (a_1 * b_1 + (a_1 + a_2) * b_2 + (a_1 + a_2 + a_3) * b_3 + …) / s^2

而易见p((a_i),(a_i)) + p((b_i),(b_i)) – 2p((a_i),(b_i))是一个平方和,所以p((a_i),(a_i)) + p((b_i),(b_i)) >= 2p((a_i),(b_i))。存在(c_i)(等于(a_i)或者(b_i)),使得同时有p((a_i),(c_i)) >= p((a_i),(b_i)),p((c_i),(b_i)) >= p((a_i),(b_i))。所以可以在D1, D2间插入骰子,使得获胜概率不变。

取有向图G中获胜概率最大的环,去掉此环外的顶点以及对应的骰子,然后再将其以上述方法插入环中。这样就得到了一个长度为n的环,并且获胜概率没有降低,证毕。

讲了这么多,其实就是说,对于最大化p(D)的非传递性骰子D,我们可以假定它有一个合法的区块表示(m_1, …, m_{n*s})。这就是非传递性骰子的一个数学模型。如果我们能找出最大化p(D)的区块表示,那么我们就找到了最大化p(D)的非传递性骰子。

我们也可以将区块表示转换为面值表示,具体的方法就是在D_1上填上m_1个1,然后在D_2上填上m_2个2,如此往复,然后在D_1上填上m_{n+1}个n+1,如此类推。

约束编程

这个寻找最大化p(D)的非传递性骰子的问题,其实是我课上的一个Project,这门课讲的是约束编程(Constraint Programming)。

约束编程是什么呢?打个比方,在普通的编程中,你需要教会电脑怎么去算某种东西;而在约束编程中,你只需要告诉电脑你需要的答案满足什么样的约束条件,一个solver就会帮你把符合这样的约束条件的答案找出来!当然,这是以性能为代价的,因为solver面对的是一般的约束问题。就像瑞士军刀虽然可以切排骨但是要费大力气,solver可以解很多一般性的问题,但是效率肯定比不上专门为某个问题写的程序。

在这个时候,一个好的模型就很重要了。一个好的约束模型可以大大减小需要搜索的解空间,从而加快搜索的速度。在我们的这个任务中,由于需要最大化p(D),所以必须搜索整个解空间(当然是会用分支限界的),所以好的约束模型尤其重要。而区块表示作为一个约束模型,因为去除了很多对称性,将要搜索的解空间变得很小。一个粗糙的实验显示,区块表示的约束模型求解速度比面值表示的约束模型要快上两三个数量级左右。

文章开头给出的例子就是n=3, s=6时的最优解。

一个猜想

在一些小的(n,s)上的实验中,我们可以发现给出的最大化p(D)的非传递性骰子D,每颗骰子上可以至多有3种面值。也就是说它的区块表示m中,m_{3n+1}=0。于是,我们有如下的猜想:

猜想:对于任意(n,s),如果n枚s面的非传递性骰子存在的话,那么一定有一套这样的骰子D,D最大化p(D),同时它的区块表示m中,m_{3n+1}=0。

谁有什么想法么?

更多资料,请参见wikipedia:http://en.wikipedia.org/wiki/Nontransitive_dice

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s