问题
Room 方(Room square):n×n 的方格(n 奇),每格或空或放 «一对» 无序点对,满足:①每个符号恰在每行、每列出现一次;②每个 «无序对» 恰出现一次。它是 «双打循环赛表» 的数学化(n+1 个队、n 轮、每轮场地不冲突)——等价于 «Kn+1 的 1-因子分解的 «对偶» 拼装»。Howell 设计 H(s,2n):Room 方的 «部分符号» 推广(s 轮、2n 队)。谱问题:参数谱何时存在?存在性判据覆盖多数同余类(Room 方存在 ⟺ n 为奇且 n ≠ 3,5——1970s 完全解决),剩余类(Howell 设计的完整谱、«极小 Room 方»)未合流。
主要概念
Room 方与 P1F 的对偶
Room 方 ⟺ «Kn+1 的 1-因子分解 + 行列的 «双正交» 排列»:行 = 因子、列 = «轮次» 的重排——«对偶» 指行与列 «对称地» 承载因子结构(18 号 P1F 的 «完美性» 在这里变成 «行列双条件»)。Room 方的存在性(n ≠ 3,5)是 «starter 加倍» 机器的胜利:«starter» 构造 + «乘积构造»(小方拼大方)覆盖所有奇 n ≥ 7。
Howell 设计的谱
Howell 设计 H(s,2n):2n 个符号、s 列(轮),每列 «n 对铺满全部 2n 符号»、每符号每列恰一次、每对至多一次——«Room 方去掉 «全部对» 的要求»。存在谱:s 的范围 2n−1 ≤ s ≤ C(2n,2)/n 内的分段已知(«下端» 与 «上端» 的判据定理),中段的完整谱未合流。
主要命题与证明
命题 1(Room 方存在定理,1970s;陈述) n 阶 Room 方存在 ⟺ n 为奇数且 n ≥ 7(n=1 平凡、n=3,5 不存在)。
说明 必要性:n=3,5 的不可存在由 «符号对数 vs 格位» 的计数与 «starter 不存在»(3,5 元集合无差覆盖 starter)给出;充分性是 «starter + 乘积» 的大工程(Stanton–Mullin–Anderson 的系列)。□
命题 2(与 P1F 的对偶翻译,完整证明) n 阶 Room 方 ⟹ Kn+1 的 1-因子分解;反之 «带 «α-标号» 的 P1F»(每因子配 «行列指标» 的双正交结构)给出 Room 方。
证明 Room 方的 «行» 是 «部分 1-因子»(每符号恰一次 ⟹ 覆盖全部 n+1 个符号中的 «成对者»):行列联合的 «每对恰一次» ⟹ «行 ∪ 列指标» 给出 Kn+1 的完整边分划——每 «行+列» 组合是一个 1-因子(«行-列对» 的 «斜» 结构),共 n 个因子(Kn+1 恰需 n 个因子)✓。反向:P1F 的因子序列 + «每因子的 «旋转指标»» 的双正交排列(«α-标号»)装配 Room 方。□
命题 3(Howell 谱的已知段;陈述) Howell 设计的参数 s 有一个 «可行区间»(下端由 «每符号每列恰一次» 的计数给出,上端由 «对数 » 的计数给出):下端与上端的判据定理已立(«上端» = «满 Howell» ⟺ Room 型条件),中段部分闭合;«极小 Room 方»(«块最少» 的变体)与 «斜 Room 方»(skew)的谱各有剩余类。
说明 斜 Room 方与 «最优 tournament 调度»、«光正交码» 相连——工程需求把 «谱的剩余类» 变成 «有真值表压力» 的开放题。□
进展与文献
Room 1955 的原始方;Stanton–Mullin–Anderson 的存在性系列;Dinitz–Stinson 的 «Room squares and Howell designs» 综述(Handbook 章);与 18 号 P1F、43 号覆盖的交叉。开放核心:Howell 谱中段;极小与斜 Room 方的完整谱;«双正交标号» 的系统理论。