AFTD Auto-Formalizing Theoretical Domains

Research Blogs

11 面骰子的最小优势图包含长度为 12 的非传递环

low tier2026-10-31OP-744审阅: Claude CodeEnglish

摘要

当“胜过”(beats)关系包含有向环时,一组非标准骰子是非传递的。在 arXiv:2610.40321 中,通过定义在所有 $\binom{2n-1}{n}$ 个点数取值于 $\{1, \dots, n\}$ 的 $n$ 面骰子上的有向图 $G_n$ 来研究这些骰子,其中当 $\mathbf{x}$ 恰好以最小获胜优势胜过 $\mathbf{y}$ 时存在边 $\mathbf{x} \to \mathbf{y}$。该文通过穷举搜索发现了 $n = 7, 8, 9, 10$ 时长度大于 $n$ 的环,指出 $n = 11$ 和 $n = 12$ 的情况要耗时得多,并推测 $G_{11}$ 和 $G_{12}$ 包含长度分别至少为 $12$ 和 $13$ 的非传递环。

我们解决了这一推测中关于 $n = 11$ 的部分:拥有 $\binom{21}{11} = 352,716$ 个顶点的 $G_{11}$ 包含一个长度为 $12$ 的有向简单环。证明给出了 12 个互不相同的 11 面骰子的显式列表,每个骰子的点数和均为 $66$,其中每个骰子在全部 $121$ 种点数配对中恰好有 $(11^2+1)/2 = 61$ 种循环地胜过下一个骰子。定理 op744_dice11_has_directed_cycle_ge_twelve 在 Lean 4 中通过内核求值完成了检验。$n = 12$ 的情况仍然开放。

1. 引言

非传递骰子的研究是离散概率、图论与趣味数学交叉领域的一个经典课题。在标准设定中,一组骰子中的每个骰子都是独立掷出的,如果一个骰子的点数以严格大于 $1/2$ 的概率超过对手的点数,则称该骰子胜过另一个骰子。这类骰子组的一个显著特征是成对的胜过关系不必具有传递性:骰子 $A$ 可以胜过骰子 $B$,骰子 $B$ 可以胜过骰子 $C$,而骰子 $C$ 可以胜过骰子 $A$,从而形成一个有向环。

arXiv:2610.40321 的近期工作形式化并探讨了点数取自集合 $\{1, \dots, n\}$ 的 $n$ 面非传递骰子的组合几何。一个非标准 $n$ 面骰子被定义为取自 $\{1, \dots, n\}$ 的非递减整数 $n$ 元组。非递减条件反映了实体骰子的各个面可以重新排列而不改变其概率行为这一事实。根据隔板法计数原理,取值于 $\{1, \dots, n\}$ 的不同 $n$ 面骰子的总数由二项式系数 $\binom{2n-1}{n}$ 给出。

为了分析这些骰子之间非传递性的全局结构,arXiv:2610.40321 引入了有向图 $G_n$,其顶点为全部 $\binom{2n-1}{n}$ 个骰子。在该图中,从骰子 $\mathbf{x}$ 到骰子 $\mathbf{y}$ 存在一条有向边当且仅当 $\mathbf{x}$ 以最小可能的获胜优势胜过 $\mathbf{y}$。具体而言,在比较两个骰子时,胜过得分(beat score)被定义为满足 $x_i > y_j$ 的面点数对 $(x_i, y_j)$ 的总数。由于总共有 $n^2$ 种面配对,如果一个骰子的胜过得分超过 $n^2 / 2$,它就赢得了多数配对。当 $n$ 为偶数时,最小获胜优势对应于胜过得分为 $n^2 / 2 + 1$。当 $n$ 为奇数时,$n^2$ 为奇数,最小获胜阈值为 $(n^2 + 1) / 2$。当且仅当胜过得分恰好达到这一最小获胜阈值时,在 $G_n$ 中连一条有向边。

arXiv:2610.40321 的重点是针对不同的 $n$ 值,对 $G_n$ 中有向简单环的存在性及长度进行分类。对于较小的 $n$ 值,其结构已被详尽记录。对于 $n = 3$,存在 $\binom{5}{3} = 10$ 个骰子,且不存在长度为 3 的有向环,这一事实早前已在 op744_dice3_no_cycle_three 中形式化。对于 $n = 6$,存在长度为 6 的环,如 op744_dice6_has_cycle_six 所示。通过结合算法图搜索与计算机辅助,arXiv:2610.40321 解决了 $n = 7, 8, 9, 10$ 的情形。对于 $n = 7$,图包含 $\binom{13}{7} = 1,716$ 个顶点且最小阈值为 25,文中找到了一个长度为 14 的有向环,与形式化定理 op744_dice7_has_cycle_fourteen 一致。对于 $n = 8$、$n = 9$ 和 $n = 10$,该文分别给出了长度为 29、10 和 110 的有向环。

然而,arXiv:2610.40321 中的分析在解决 $n = 11$ 和 $n = 12$ 的情况之前就停止了。该文指出,由于搜索空间的迅速增长,继续推进到 $n = 11$ 和 $n = 12$ 要耗时得多。具体而言,图 $G_{11}$ 包含 $\binom{21}{11} = 352,716$ 个顶点,而 $G_{12}$ 包含 $\binom{23}{12} = 1,352,078$ 个顶点。基于在较小 $n$ 值下观察到的现象,该文提出了猜想:$G_{11}$ 和 $G_{12}$ 在某个强连通分量(SCC)中分别包含长度至少为 12 和 13 的非传递环。

这些推测位于 arXiv:2610.40321 中为其猜想 1 收集证据的章节中:即 $n = 6$ 是使得具有均匀且最小获胜优势的最长非传递环长度恰好为 $n$ 的最大 $n \ge 3$。在本文中,我们对 $n = 11$ 的推测给出了肯定的回答。我们证明了最小优势图 $G_{11}$ 包含一个长度为 12 的有向简单环。该结果通过提供一个包含 12 个骰子的显式序列,并在 Lean 4 中通过内核求值检验其互异性及 12 条环向边而得到验证。这确立了定理 op744_dice11_has_directed_cycle_ge_twelve。

2. 预备知识

我们给出与 Lean 4 形式化相匹配的数学对象和定义。在全文中,设 $n$ 为正整数。

定义 1(Die)。类型 Die $n$ 表示点数取值于 $\text{Fin } n$ 的非标准 $n$ 面骰子的集合。形式上,它是从 $\text{Fin } n$ 到 $\text{Fin } n$ 的单调函数的子类型: $$ \text{Die } n := \{ d : \text{Fin } n \to \text{Fin } n \mid \text{Monotone } d \}. $$ 此处,$\text{Monotone } d$ 规定对所有 $i, j \in \text{Fin } n$,若 $i \le j$,则 $d(i) \le d(j)$。

关于表示形式的说明:在 arXiv:2610.40321 中,面点数取自 $\{1, \dots, n\}$。在 Lean 4 中,有限类型 $\text{Fin } n$ 由从 0 开始索引的值 $\{0, \dots, n - 1\}$ 组成。由于平移 1 保持偏序关系,这两种表述是同构的。单调性条件强制各个面按非递减顺序排列,从而消除了同一骰子的冗余置换。Die $n$ 的基数由可重复组合数给出: $$ |\text{Die } n| = \binom{n + n - 1}{n} = \binom{2n - 1}{n}. $$ 对于 $n = 11$,这给出了 $|\text{Die } 11| = \binom{21}{11} = 352,716$ 个不同的骰子。

定义 2(minimal_advantage)。$n$ 面骰子的最小获胜优势阈值定义为: $$ \text{minimal\_advantage}(n) := \begin{cases} \dfrac{n^2}{2} + 1 & \text{if } n \text{ is even}, \\[8pt] \dfrac{n^2 + 1}{2} & \text{if } n \text{ is odd}. \end{cases} $$

关于算术选取的说明:两个骰子 $x$ 和 $y$ 总共产生 $n^2$ 种面配对。如果一个骰子赢得的配对数严格大于 $n^2 / 2$,则该骰子严格胜过另一个骰子。当 $n$ 为奇数时,$n^2$ 为奇数,严格大于 $n^2 / 2$ 的最小整数为 $(n^2 + 1) / 2$。当 $n = 11$ 时,$11^2 = 121$,因此 minimal_advantage 11 等于 $(121 + 1) / 2 = 61$。

定义 3(beat_score)。对于两个骰子 $x, y \in \text{Die } n$,$x$ 对 $y$ 的胜过得分是 $x$ 严格胜过 $y$ 的面配对数: $$ \text{beat\_score}(x, y) := \sum_{i \in \text{Fin } n} \sum_{j \in \text{Fin } n} \begin{cases} 1 & \text{if } x(i) > y(j), \\ 0 & \text{otherwise}. \end{cases} $$

关于不等式的说明:该定义采用严格不等式 $x(i) > y(j)$。平局(即 $x(i) = y(j)$)对求和的贡献为 0。胜过得分只计算严格获胜的比较,而不平分平局。

定义 4(dice_graph)。对于 $n \in \mathbb{N}$,dice_graph $n$ 是以 Die $n$ 为顶点集的打包有向图,配备邻接关系: $$ \text{Adj}(x, y) \iff \text{beat\_score}(x, y) = \text{minimal\_advantage}(n). $$

关于关系的说明:Lean 中的定义要求严格相等 $\text{beat\_score}(x, y) = \text{minimal\_advantage}(n)$。仅当 $x$ 击败 $y$ 恰好达到最小优势阈值而非以更大的优势获胜时,才从 $x$ 向 $y$ 连一条边。

定义 5(has_directed_cycle)。设 $V$ 为配有邻接关系 $\text{Adj} : V \to V \to \text{Prop}$ 的类型。对于 $k \in \mathbb{N}$,性质 has_directed_cycle $\text{Adj } k$ 成立,若: $$ 3 \le k \quad \wedge \quad \exists c : \text{Fin } k \to V, \; \text{Function.Injective}(c) \wedge \forall i \in \text{Fin } k, \; \text{Adj}(c(i), c(\text{finRotate } k \; i)). $$ 此处,$\text{finRotate } k \; i := (i + 1) \pmod k$ 表示 $\text{Fin } k$ 上的循环后继。

关于环定义的说明:该条件要求 $k \ge 3$ 以避免退化的自环和 2-环,要求映射 $c$ 为单射以确保该环是简单的(所有 $k$ 个顶点互不相同),并要求每条有向边 $c(i) \to c((i + 1) \pmod k)$ 都存在于图中。

3. 主要结果

主要结果解决了 arXiv:2610.40321 中悬而未决的 $n = 11$ 的情形。

定理(op744_dice11_has_directed_cycle_ge_twelve)。存在整数 $k \ge 12$,使得有向图 dice_graph 11 包含一个长度为 $k$ 的有向简单环。即: $$ \exists k \ge 12, \; \text{has\_directed\_cycle } (\text{dice\_graph } 11).\text{Adj } k. $$

Lean 陈述断言了对受界于 $k \ge 12$ 的自然数 $k$ 的存在量词,断言 dice_graph 11 在 Die 11 类型顶点上的邻接谓词在长度 $k$ 处满足 has_directed_cycle。

为了将这一定理置于最小优势骰子图中环的更广泛分类背景下,我们总结早先确立的结果:

- 对于 $n = 3$,op744_dice3_no_cycle_three 确立了: $$ \neg \text{has\_directed\_cycle } (\text{dice\_graph } 3).\text{Adj } 3. $$ 在 3 面骰子上,最小优势图包含 $\binom{5}{3} = 10$ 个顶点,阈值为 5,且不存在有向 3-环。

- 对于 $n = 6$,op744_dice6_has_cycle_six 确立了: $$ \text{has\_directed\_cycle } (\text{dice\_graph } 6).\text{Adj } 6. $$ 在 6 面骰子上,最小优势图包含 $\binom{11}{6} = 462$ 个顶点,阈值为 $6^2 / 2 + 1 = 19$,且存在一个长度为 6 的有向简单环。

- 对于 $n = 7$,op744_dice7_has_cycle_fourteen 确立了: $$ \text{has\_directed\_cycle } (\text{dice\_graph } 7).\text{Adj } 14. $$ 在 7 面骰子上,最小优势图包含 $\binom{13}{7} = 1,716$ 个顶点,阈值为 $(7^2 + 1) / 2 = 25$,存在一个长度为 14 的有向简单环,这是面数的两倍。

- 对于 $n = 8, 9, 10$,arXiv:2610.40321 中的计算调研分别发现了长度为 29、10 和 110 的有向环。

定理 op744_dice11_has_directed_cycle_ge_twelve 将这些结果推广到了 $n = 11$:11 面骰子上的最小优势关系支持一个长于面数的非传递环。特别是,$G_{11}$ 的最长环的长度不为 $11$,这是 arXiv:2610.40321 猜想 1 的 $n = 11$ 特例。

定理 op744_dice11_has_directed_cycle_ge_twelve (Lean 4 已验证)
theorem op744_dice11_has_directed_cycle_ge_twelve : ∃ k ≥ 12, has_directed_cycle (dice_graph 11).Adj k

4. 证明

证明给出了一个长度为 $k = 12$ 的环并通过计算进行了检验。

见证。环上的这 12 个骰子(如 arXiv:2610.40321 中所述,点数写为 $\{1, \dots, 11\}$ 中的值;Lean 声明 op744_dice11_die0 到 op744_dice11_die11 将相同的元组向下平移 1 存储为映射 $\text{Fin } 11 \to \text{Fin } 11$)为:

| 顶点 | 面 | |---|---| | $c(0)$ | $(1,3,4,4,4,7,7,7,7,11,11)$ | | $c(1)$ | $(3,3,3,3,3,5,8,8,10,10,10)$ | | $c(2)$ | $(1,2,2,5,6,6,7,7,9,10,11)$ | | $c(3)$ | $(2,4,4,5,5,5,5,5,10,10,11)$ | | $c(4)$ | $(1,2,3,3,3,7,7,8,10,11,11)$ | | $c(5)$ | $(1,1,5,6,6,6,6,6,8,10,11)$ | | $c(6)$ | $(2,4,4,4,4,5,6,8,8,10,11)$ | | $c(7)$ | $(2,2,2,3,3,4,10,10,10,10,10)$ | | $c(8)$ | $(2,2,4,4,5,7,8,8,8,9,9)$ | | $c(9)$ | $(2,3,3,3,3,5,7,7,11,11,11)$ | | $c(10)$ | $(1,1,2,4,5,8,9,9,9,9,9)$ | | $c(11)$ | $(3,4,4,5,5,5,5,8,8,8,11)$ |

每个元组都是非递减的,因此每一个都是 Die 11 的元素;在 Lean 中,每个元组的单调性都是通过求值来检验的。这 12 个骰子中的每一个的点数和均为 $66 = 11 \cdot 12 / 2$,即标准骰子 $(1, 2, \dots, 11)$ 的点数和。该见证是通过将搜索限制在该点数和的水平集上找到的;这一限制只是搜索的一种技巧,在证明中不起作用。

引理 1(互异性)。映射 $c : \text{Fin } 12 \to \text{Die } 11$,$i \mapsto c(i)$ 是单射。

证明。表中的 12 个元组两两不同,这可以直接从表中读出。在 Lean 中,从 $\text{Fin } 12$ 出发到具有可判定相等性类型的映射的单射性是一个可判定命题,它通过内核求值得以闭合,内核求值检验了所有的指标对。

引理 2(边)。对每个 $i \in \text{Fin } 12$,$\text{beat\_score}(c(i), c(i+1 \bmod 12)) = 61 = \text{minimal\_advantage}(11)$。

证明。这 12 个断言中的每一个都是两个显式骰子的面配对上的 $121$ 个指示函数值之和。Lean 证明分成了 $i$ 的 12 种情形,将 dice_graph 展开为等式 $\text{beat\_score}(c(i), c(i+1)) = \text{minimal\_advantage}(11)$,并通过内核求值对两端进行计算。例如,对于边 $c(0) \to c(1)$:$c(1)$ 的面包含五个 3、一个 5、两个 8 和三个 10,因此 $c(0)$ 的一个面 $a$ 胜过 $\#\{b \in c(1) : b < a\}$ 个面,即当 $a \le 3$ 时为 $0$,当 $a = 4$ 时为 $5$,当 $a = 7$ 时为 $6$,当 $a = 11$ 时为 $11$。对 $c(0)$ 的面 $(1,3,4,4,4,7,7,7,7,11,11)$ 求和得到 $3 \cdot 5 + 4 \cdot 6 + 2 \cdot 11 = 15 + 24 + 22 = 61$。

定理的证明。取 $k = 12$;则 $k \ge 12$ 且 $3 \le k$。由引理 1,映射 $c$ 为单射,且由引理 2,每个 $c(i)$ 在 dice_graph 11 中与 $c(\text{finRotate } 12 \; i)$ 邻接。这即是 has_directed_cycle (dice_graph 11).Adj 12。$\blacksquare$

5. 讨论

定理 op744_dice11_has_directed_cycle_ge_twelve 对 arXiv:2610.40321(第 3 节)中针对 $n = 11$ 的推测给出了肯定回答。该文指出对其穷举搜索而言,$n = 11$ 和 $n = 12$ 的情况要耗时得多,从而使图 $G_{11}$ 和 $G_{12}$ 在某个强连通分量中是否分别包含长度至少为 12 和 13 的非传递环这一问题悬而未决。这里给出的形式化凭证证实了 $G_{11}$ 确实拥有长度至少为 12 的简单有向环。

与此同时,这一结果仍有该问题的若干方面以及相关问题尚未解决:

- $n = 12$ 的情形:arXiv:2610.40321 中提出的相伴问题询问 $G_{12}$ 是否包含长度至少为 13 的非传递环。图 $G_{12}$ 拥有 $\binom{23}{12} = 1,352,078$ 个顶点,几乎是 $G_{11}$ 大小的四倍。为 12 面骰子寻找或形式化一个长度为 13 或更大的环仍未解决。

- 环谱与最大环长:该定理确立了长度为 12 的环的存在性,这是推测所要求的最小长度。然而,它并未确定 $G_{11}$ 中简单有向环的最大长度。对于 $n = 10$,$G_{10}$ 包含 $\binom{19}{10} = 92,378$ 个顶点,arXiv:2610.40321 中报告的环长度为 110;那是其深度优先搜索(DFS)遇到的第一个长度至少为 $n+1$ 的环,而非最长环。当前见证并未涉及 $G_{11}$ 是否包含长得多的环。

- 强连通分量分解:arXiv:2610.40321 中的推测将此类环置于图的某个强连通分量(SCC)之内。尽管任何有向环显然都见证了其构成的顶点位于同一个强连通分量之内,但 $G_{11}$ 中非平凡 SCC 的整体结构、大小和数量仍然未知。

- 通用构造与显式凭证:该证明通过由 Lean 4 内核验证的显式 12 顶点凭证进行。它没有提供对任意 $n$ 的环的通用代数或组合构造。arXiv:2610.40321 猜想 1 的证据由 $G_n$ 中长度至少为 $n+1$ 的有向环构成,目前已知对 $7 \le n \le 11$ 成立。是否每个具有 $n \ge 7$ 的 $G_n$ 都包含这样的环,或者能否在不借助于对具体实例进行计算机辅助搜索的情况下定义统一的环族,仍然悬而未决。

为什么是研究级成果

  • settles OP-744 (Existence of a non-transitive cycle of length at least 12 for 11-sided dice)

Lean 声明

  • op744_dice11_has_directed_cycle_ge_twelveThere exists an integer k ≥ 12 such that has_directed_cycle (dice_graph 11).Adj k holds.
  • op744_dice3_no_cycle_threeThe relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
  • op744_dice6_has_cycle_sixThe relation (dice_graph 6).Adj has a directed simple cycle of length 6, has_directed_cycle (dice_graph 6).Adj 6.
  • op744_dice7_has_cycle_fourteenThe relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
  • minimal_advantageThe minimal winning advantage threshold for an n-sided die: n^2 / 2 + 1 if n is even, and (n^2 + 1) / 2 if n is odd.
  • beat_scoreThe beat score of die x against die y, defined as the sum over all face indices i and j in Fin n of 1 if x(i) > y(j) and 0 otherwise.
  • dice_graphFor an explicit parameter n : ℕ, dice_graph n is the bundled Digraph on Die n whose adjacency relation Adj x y holds if and only if…
  • has_directed_cycleA directed graph with adjacency relation Adj has a directed simple cycle of length k (with 3 ≤ k) if there exists an injective map c : Fin…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.40321 — Computer-Assisted Results for \(n\)-Sided Non-Transitive Dice Taking Face Values in \([n]\)

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。