给定一个从 23 个数字中选取 7 个数字的彩票,如果匹配至少 4 个数字即可获得奖金,则存在一组 253 张彩票,保证中奖。这组彩票对应于 Witt 设计。
更正式地,23 个点上的 Witt 设计是一个 4-(23,7,1) 区组设计 (Witt 1938)。它是组合数学中最引人注目的结构之一 (Godsil and Royle 2001)。它可以通过将 在 GF(2) 上分解为
来构造,其中
然后计算 2048 个幂 、
、
、 ...、
,模
。这组向量恰好是 [23,12,7] 格雷码,具有 253 个权重为 7 的向量、1288 个权重为 11 的向量和 506 个权重为 15 的向量。例如,
是一个权重为 7 的向量。
Witt 设计是作用于 23 个点的 253 个权重为 7 的向量的集合。
考虑顶点为 253 个向量 () 和 23 个点 (
)。设置边,使得如果
,则
相邻;如果
共享一个项,则它们相邻。选择一个任意顶点。对于该顶点的所有 176 个邻居,将边更改为非边,将非边更改为边。消除现在孤立的顶点,剩下的 275 个顶点图是 McLaughlin 图,一个 距离正则图。
从 Witt 设计中,77 个向量包含 0(0 是从 0-22 中任意选择的)。消除 0()得到大小为 77 的唯一 Steiner 系统
,作用于点 1 到 22。考虑顶点为 77 个向量 (
),如果
不共享项则相邻。这给出了一个 77 顶点图,称为 M22 图。
考虑顶点为 77 个向量 ()、22 个点 (
) 和新符号
。设置边,使得
与所有
相邻;如果
,则
相邻;如果
不共享项,则它们相邻。得到的 100 顶点图是 Higman-Sims 图,一个 距离正则图。
从上面 77 个向量上的 中,令不包含任意选择的点 22 的 56 个向量为顶点,并连接不相交的顶点。这构建了 Gewirtz 图,一个具有相交数组
的 56 个节点的 距离正则图。
大 Witt 设计是 格雷码 的 759 个权重为 8 的向量,通常称为八元组。大 Witt 图 将大 Witt 设计的 759 个向量视为顶点,边连接不相交的向量。这是一个具有相交数组 的 距离正则图。
截断 Witt 图 在 506 个点上构建,方法是删除大 Witt 设计中包含任意选择的符号的所有向量。这产生了一个具有相交数组 的 距离正则图。
双重截断 Witt 图 在 330 个点上构建,方法是删除大 Witt 设计中包含任意选择的两个符号的所有向量。这是一个具有相交数组 的 距离正则图。
类似的构造在 上分解
,产生 Leech 格 的
个向量 (Conway and Sloane 1999)。