Project Euler 376

发表于 分类于 阅读次数： 本文字数： 4k 阅读时长 ≈ 4 分钟

Project Euler 376

题目

Nontransitive sets of dice

Consider the following set of dice with nonstandard pips:

Die \(A: 144444\)

Die \(B: 222555\)

Die \(C: 333336\)

A game is played by two players picking a die in turn and rolling it. The player who rolls the highest value wins.

If the first player picks die \(A\) and the second player picks die \(B\) we get

\(P(\text{second player wins}) = \dfrac{7}{12} > \dfrac{1}{2}\)

If the first player picks die \(B\) and the second player picks die \(C\) we get

\(P(\text{second player wins}) = \dfrac{7}{12} > \dfrac{1}{2}\)

If the first player picks die \(C\) and the second player picks die \(A\) we get

\(P(\text{second player wins}) = \dfrac{25}{36} > \dfrac{1}{2}\)

So whatever die the first player picks, the second player can pick another die and have a larger than \(50\%\) chance of winning.

A set of dice having this property is called a nontransitive set of dice.

We wish to investigate how many sets of nontransitive dice exist. We will assume the following conditions:

  • There are three six-sided dice with each side having between \(1\) and \(N\) pips, inclusive.
  • Dice with the same set of pips are equal, regardless of which side on the die the pips are located.
  • The same pip value may appear on multiple dice; if both players roll the same value neither player wins.
  • The sets of dice \(\{A,B,C\}, \{B,C,A\}\) and \(\{C,A,B\}\) are the same set.

For \(N = 7\) we find there are \(9780\) such sets.

How many are there for \(N = 30\) ?

解决方案

两枚六面骰 \(X,Y\) 各掷一次共有 \(36\) 种等可能结果。令

  • \(W(Y>X)\)：满足 \(Y\) 点数严格大于 \(X\) 的结果数；
  • \(G(X\ge Y)\)：满足 \(X\) 点数大于等于 \(Y\)（包含平局）的结果数。

显然有恒等式\(W(Y>X)+G(X\ge Y)=36\)。题目要求“后手胜率严格大于 \(1/2\)”等价于\(\dfrac{W(Y>X)}{36}>\dfrac12 \Longleftrightarrow W(Y>X)>18 \Longleftrightarrow G(X\ge Y)<18.\)

对三枚骰 \((A,B,C)\)，若无论先手选哪一枚，后手总能选另一枚使胜率 \(>1/2\)，在 3 点有向完全图中必然形成一个三环（因为“\(>1/2\)”是严格且反对称）。因此可固定方向，只统计满足\(P(B>A)>\dfrac12, P(C>B)>\dfrac12, P(A>C)>\dfrac12\)的有序三元组 \((A,B,C)\)，最后再除以 3 消去循环平移等价（\({A,B,C}\sim{B,C,A}\sim{C,A,B}\)）。

利用上面的等价形式，这个方向化条件等价于三个不等式\(G(A\ge B)<18, G(B\ge C)<18, G(C\ge A)<18.\)

把三枚骰上出现过的所有点数去重并按从小到大排序，得到\(v_1<v_2<\cdots<v_k.\)接下来进行离散化：把每个取值 \(v_t\) 映射为一个等级编号 \(t\)，也就是将所有等于 \(v_t\) 的面统一替换为“等级” \(t\)。这样一来，任意两面的比较结果只取决于等级之间的 \(<,=,>\) 关系，而与具体数值的大小差距无关；因此诸如 \(G(\cdot\ge\cdot)\) 这类计数只依赖于离散化后的“等级结构”。

反过来，给定一个使用了 \(k\) 个等级的结构，要恢复到原问题中的具体点数，只需从集合 \({1,2,\dots,N}\) 中选择 \(k\) 个严格递增的整数分别赋给等级 \(1,2,\dots,k\)（即作为 \(v_1,\dots,v_k\)）。这样的赋值方案数正是\(\dbinom{N}{k}.\)因此整体计数可以表述为：对所有可行的等级结构求和，每个结构按照其使用等级数 \(k\) 贡献权重 \(\dbinom{N}{k}\)。接下来只需设计一个 DP 来枚举并计数所有满足三条 \(<18\) 约束的等级结构，再将对应的权重累加即可。

对每个等级 \(t\)，记它在三枚骰上的出现次数为\((a_t,b_t,c_t), a_t,b_t,c_t\in\{0,1,\dots,6\}, a_t+b_t+c_t\ge 1.\)并满足总面数约束\(\displaystyle{\sum_{t=1}^k a_t=6, \sum_{t=1}^k b_t=6, \sum_{t=1}^k c_t=6.}\)

我们按 \(t=1,2,\dots\)（从最小等级到最大等级）依次决定 \((a_t,b_t,c_t)\)。

定义三项“坏计数”（对应三条胜率约束）：\(L_A = G(C\ge A), L_B = G(A\ge B), L_C = G(B\ge C).\)最终我们需要\(L_A<18, L_B<18, L_C<18.\)设在某一步之前，尚未分配等级的面数分别为\(a,b,c\)（即将来会被赋予当前等级或更大等级的面数），并且坏计数当前为 \((L_A,L_B,L_C)\)。

现在我们为“当前最小的尚未出现的等级”分配\((a',b',c'), 0\le a'\le a,0\le b'\le b,0\le c'\le c, a'+b'+c'\ge 1.\)

关键：由于当前等级是目前最小的等级，所有尚未分配的面将来拿到的等级都不小于当前等级，因此与当前等级面比较时必然满足未分配面 \(\ge\) 当前等级。于是产生如下必然配对贡献：

  • \(L_B=G(A\ge B)\)：当前新增的 \(b'\) 个 \(B\) 面为当前等级，与所有“尚未分配的 \(A\) 面”（数量为旧的 \(a\)）配对都满足 \(A\ge B\)，贡献增量 \(b'\cdot a\)。
  • \(L_C=G(B\ge C)\)：增量为 \(c'\cdot b\)。
  • \(L_A=G(C\ge A)\)：增量为 \(a'\cdot c\)。

同时未分配面数更新为\((a,b,c)\leftarrow(a-a',b-b',c-c').\)

最终，我们令\(F(k,a,b,c,L_A,L_B,L_C)\)表示：已经使用了 \(k\) 个等级（已决定了前 \(k\) 个最小等级的分配），当前尚未分配的面数为 \((a,b,c)\)，当前坏计数为 \((L_A,L_B,L_C)\) 时，从该状态继续完成所有等级分配所能得到的总贡献（即已经把最终的 \(\dbinom Nk\) 权重也考虑进来）。这里的“总贡献”最终会被加总得到方向化计数。

那么可以写出状态转移\(F\)的状态转移方程如下：

\[ F(k,a,b,c,L_A,L_B,L_C)= \left\{\begin{aligned} &0 &&\text{if}\quad \max\{L_A,L_B,L_C\}\ge 18 \\ &\binom{N}{k} &&\text{else if}\quad a=b=c=0 \\ &\displaystyle\sum_{\substack{0\le a'\le a\\0\le b'\le b\\0\le c'\le c\\a'+b'+c'\ge 1}} F(k+1,a-a',b-b',c-c',L_A+a'\cdot c,L_B+b'\cdot a,L_C+c'\cdot b) &&\text{else.} \end{aligned}\right. \]

方程第一行则表示任何一条坏计数若已达到或超过 18，则该方向化三环不可能成立（因为坏计数只会增加不会减少）。方程第二行则表示当所有面都已分配完，说明我们已经构造出一个完整等级结构，并使用了 \(k\) 个不同等级。该结构映射到真实点数的方式数为 \(\dbinom Nk\)。第三行则表示枚举当前等级在三骰上的分配 \((a',b',c')\)并进行转移。

最终方向化计数得到￥\(F(0,6,6,6,0,0,0)\)，把循环平移视作同一集合，因此最终答案为\(\dfrac{1}{3}F(0,6,6,6,0,0,0)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from functools import lru_cache
from tools import comb

N = 30
def count_nontransitive_sets(N: int) -> int:
    """
    计算题目所求：三枚六面骰点数在 1..N 的所有非传递骰组数量，
    其中 {A,B,C}、{B,C,A}、{C,A,B} 视为同一组（循环平移等价）。
    """

    # 枚举分配三元组 (a',b',c') 的列表：给定剩余 (a,b,c)，当前等级至少出现一次
    splits = {}
    for a in range(7):
        for b in range(7):
            for c in range(7):
                lst = []
                for aa in range(a + 1):
                    for bb in range(b + 1):
                        for cc in range(c + 1):
                            if aa + bb + cc > 0:
                                lst.append((aa, bb, cc))
                splits[(a, b, c)] = lst

    @lru_cache(maxsize=None)
    def F(k: int, a: int, b: int, c: int, LA: int, LB: int, LC: int) -> int:
        # 剪枝：坏计数达到 18 则不可能满足严格 > 1/2
        if LA >= 18 or LB >= 18 or LC >= 18:
            return 0

        # 终止：全部分配完，贡献 C(N,k)
        if a + b + c == 0:
            return comb(N, k)

        res = 0
        # 转移：为“当前最小尚未出现等级”分配 (a',b',c')
        for aa, bb, cc in splits[(a, b, c)]:
            res += F(
                k + 1,
                a - aa, b - bb, c - cc,
                LA + aa * c,   # L_A = G(C >= A)
                LB + bb * a,   # L_B = G(A >= B)
                LC + cc * b    # L_C = G(B >= C)
            )
        return res

    oriented = F(0, 6, 6, 6, 0, 0, 0)
    return oriented // 3


print(count_nontransitive_sets(N))