給定一個從 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)。