赛程安排中的数学问题

第2 0 卷 第5 期 工 程 数 学 学 报 年 3 月 J OURNAL OF ENGI NEERI NG MAT HEMATI CS V0 1 2 0 No 5 Ma r 2 0 0 3 文 章 编 号 1 0 0 5 3 0 8 5 2 0 0 3 0 5 0 1 3 0 0 4 赛程安排中的数学问题 姜 启 源 清 华 大 学 北 京 1 0 0 0 8 4 摘要 本文 结合 论文 评 阅中发 现的 问题 对赛程 安排 这道题 目给 出了一般 性结 果 并提 出可进 一 步研究 的问题 关键词 赛程 安排 每 两场 比赛 问相 隔场 次数 分 类号 AM S 2 O O O 6 8 M2 0 中图 分类号 0 2 2 6 文献标 识码 A 许 多体 育 比赛都要安 排 比赛 日程 抛开宣传 商业等方面 的考 虑 对各参赛 队的公平 性应该成 为赛程安排是 否妥 当最重要 的标准之一 这道赛题 的 目的是讨 论最简单 的一种 比 赛 单循 环赛 的赛 程安排问题 赛题从 5支球 队 的赛程安 排出发 要 求各 队每两场 比赛 中间至少相 隔一 场 用多种 方 法 甚 至凑 的方法 都能给 出一个 达到要求 的赛 程 表 1就是 一种 可 以发现 尽管 用不 同方法排 出的赛程 表 1 左部 不尽 相同 但是 每两 场 比赛 间相隔场次数及 总相隔场次数 表 1中 右部 是一样 的 不计 A B C D E的次序 这 就是 说 每 两场 比赛 最小 相隔 场次 的上界是 1 最大 相隔场次 的下 界是 2 总相隔场 次数最 小是 1 3 3 最 大是 2 3 6 下 面将会 看到 这种性质 可 以推广到任意奇数支球队 表 1 A B C D E 每 两场 比赛 间相 隔场 次数 总相 隔场 次数 A X 1 6 9 3 1 2 2 5 B 1 X 4 7 1 O 2 2 2 6 C 6 4 X 2 8 1 1 1 3 D 9 7 2 X 5 2 1 1 4 E 3 1 0 8 5 X 1 2 1 4 1 n支 球 队赛 程 安排 的一 般结 果 题 目中 2 问的是 各 队每两场 比赛 中间相 隔的场 次数的上限是多少 这 一问法稍有 含 混 确切 的提法应为 各 队每两 场 比赛 最小相隔场 次的上界 如 5支 球队赛程安排 表 1 中 的 1 实 际上 题 目 中 1 是 为 2 作 铺 垫 的 上 下联 系起 来 应 该 有 正 确 的 理 解 记各 队每两 场 比赛最小相 隔场 次为 r 用多种方法可 以证 明 r 的上界是 0 表 二 示取整数部分 评阅 中看到 的最 简单 的一种证 明是 不分 凡的奇偶 设赛 程 中某场 比赛 是 i 两 队 队参加 的下一场 比赛是 i 两 队 要使各 队 维普资讯 更多数学建模资料请关注微店店铺 数学建模学习交流 第 5期 赛 程安 排 中的数 学 问题 1 3 1 每两 场 比赛最小相 隔场次为 r 则上述两 场 比赛之 间必须有 除 以外 的 2 r 支球 队参 一 赛 于是 n 2 r 3 注意到 r 为整数 即得 r 厶 证 明这个上界可 以达到 的办法是构造性 的 即对任 意的 n编排 出达 到该上界 的赛 程 虽 然题 目只要求给 出 n 8 9的情况 但 是确有一些参赛 队对任意 的 n作 出 了或繁或 简的编 制方案 按照他 们 的办法确 实可 以达到这个上界 本 刊发表 的两篇 优秀论文都给 出了比较简 便的方法 两 队对于 n为偶数 时的方 法基本上 是一样 的 对于 n为奇 数时则有 所差别 读者 可 以查阅这两篇文章 这里 就不再对赛 程的编排方法 进行讨 论 如果考察一下 n 8 9时 的具体结 果 会发现一些似 乎有规律 的现象 n 8时最 小相隔场次数 的上限为 2 It 9时最小相 隔场 次数 的上限 为 3 按 照上述两 篇优秀论文 的方法可 以分别得 到如表 2 表 3的结果 许 多参赛队都得 到类似 的结果 只是可 能 与 表 2 表 3的左 部 不 尽 相 同 表 2 A l A 2 A 3 A 4 A 5 A 6 A 7 A 8 每 两场 比赛相 隔场 次数 相 隔场 次总数 A l 1 5 9 1 3 1 7 2 1 2 5 3 3 3 3 3 3 1 8 A 2 1 2 0 6 2 3 1 1 2 6 1 6 4 4 4 3 2 2 1 9 A 3 5 2 0 2 4 1 0 2 7 1 5 2 2 4 4 4 3 2 1 9 A 9 6 2 4 2 8 2 4 3 1 9 2 2 4 4 4 3 1 9 A 5 1 3 2 3 1 0 2 8 4 1 8 7 2 2 2 4 4 4 1 8 A 6 1 7 1 1 2 7 1 4 4 8 2 2 3 2 2 2 4 4 1 7 A 7 2 1 2 6 1 5 3 1 8 8 1 2 4 3 2 2 2 4 1 7 A 8 2 5 1 6 2 1 9 7 2 2 1 2 4 4 3 2 2 2 1 7 表 3 AI A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 每 两场 比赛相 隔 场 次数 相 隔场 次 总数 A l 3 6 6 3 1 1 1 2 6 1 6 2 1 1 4 4 4 4 4 4 4 2 8 A 2 3 6 2 2 7 7 2 2 1 2 1 7 3 2 4 4 4 4 4 4 3 2 7 A 3 6 2 3 5 1 5 3 0 2 0 2 5 1 0 3 3 4 4 4 4 4 2 6 A 4 3 1 2 7 3 5 3 1 8 8 1 3 2 3 4 4 4 4 3 3 3 2 5 1 1 7 1 5 3 3 4 2 4 2 9 1 9 3 3 3 3 4 4 4 2 4 A6 2 6 2 2 3 O 1 8 3 4 4 9 1 4 4 4 3 3 3 3 3 2 3 A 1 1 6 1 2 2 0 8 2 4 4 3 3 2 8 3 3 3 3 3 3 4 2 2 A 8 2 1 1 7 2 5 1 3 2 9 9 3 3 5 3 3 3 3 3 3 3 2 1 A 9 1 3 2 1 0 2 3 1 9 1 4 2 8 5 3 4 3 4 3 4 3 2 4 从表 2 表 3的中部可 以看 到 n 8 时每两场 比赛 相隔场次数只有 2 3 4 7 9时每两 场 比赛 相隔场次数 只有 3 4 按照上述两篇优秀论文 的方法 以上结 果可 以推广 n为偶数时 每 两 场 比 赛 相 隔 场 次 数 只 有 号一 2 号一 l 号 n 为 奇 数 时 只 有 3 2 衡 量 赛 程优 劣 的其 它 指标 除 了 各 队每两场 比赛最小 相隔场次的上界 这一指标外 还可 以用一 些指标来 衡量赛 程 的优劣 如 1 平 均相隔场次 维普资讯 1 3 2 工程数学学报 第 2 0卷 记第 i队第 个间隔场次数为 c i 1 2 n 1 2 n一2 则平均相隔场次为 i 1 c 是赛程 整体 意义下 的指标 它越 大越好 而 1 式右端的求 和就是表 2 表 3 最后一列之和 检查 n 8的赛程 表 2 得 3 检查 n 9的赛程 表 3 得 2 2 0 6 3 3 4 9 实 际 上 可 以得 到 的上 界 为 n k 一 1 n 2k 上述结 果表 明 表 2 表 3给 出的赛程都 已达到 了这个上界 2 相隔场次 的最 大偏差 赛 程 中各 队每两 场 比赛相隔场次 的 均匀性 可 由 c 与 的偏差来度量 定义 f m a x l c 一 l 3 g m a x l c 一 n 一 2 l 4 为整个赛程 相隔场次 的最大 偏差 g为球 队之间 相隔 场次 的最大 偏差 它们 都是越 小越 好 检 查 n 8的赛程 表 2 得 f 1 g 1 检查 n 9的赛程 表 3 得 f 0 5 g 5 5 实 际 上 可 以得 到 的下 界 为 f o n 2 k 1 n 2k 及 n 2 k时 g 的下 界 为 g 1 6 上述结果表 明 表 2给 出的赛程达 到了 和 g下界 表 3给出 的赛程也达 到了 的下界 3 若 干 问题 评 阅中发 现的问题之一是对 各 队每两 场 比赛 中间相 隔 的场 次数 的上 限 的理解 和确 定 事实上 只要把 握住这道题 的 目的是要 编排对各 队尽量公 平 的赛程 再 加上对 5支球 队 赛程 的分析 就应该有正 确的理解 有 的参赛 队把它理解 为 各 队每两 场 比赛 最大相 隔场次 的下界 如 5支球 队赛程安 排 表 1 中的 2 这样虽有误解 但是只要 以下正确地按照这个 理解 去作 赛程 安排 自然会 达到 各 队每两场 比赛最小相隔场次 的上界 评 阅中考虑到 了这 一 点 一 有些 队没有得 到或者没有能够证明最小相隔场次的上界是 这样 编出的 n 8和 二 n 9的赛程一般不会好 即 n 8时最小相隔场次小于 2 n 9时最小相隔场次小于 3 对 于那些既给 出了 最小相 隔场次上 界 的正确的证明 当然方法 有繁有 简 也 编排 出 达到题 目要求 的 n 8和 n 9的赛程 的论 文 评阅 中将更高 的奖项 给了在 以下几方面作得 较 好 的 队 1 n 8的赛程 中各 队每两场 比赛相隔场次数只有 2 3 4 n 9的赛 程 中各 队每两场 维普资讯 第 5期 赛程安 排 中的数 学 问题 比赛相 隔场次数 只有 3 4 2 赛 程的编制方法 能够推广到任意数 n的情况 3 对衡 量赛程优劣 的其它指标的讨论 比较充分 顺便指 出 其它指标 的讨论是开放性 的 只要能合理 地衡 量赛程 的优 劣就行 如有的队 n 一2 f c 一 f 用 d 上 一 其 中 为 c 的平均值 表示平 均相 对离差 d越小越 n n一 一i 1 ci 好 有 的队考虑到 比赛 场次靠后的 队比场次靠前的队获得的信息要多 于是引入所谓平均信 m a x S A 一 m a x S A n 一 1 息度 一 其 中 S A n n 为 i 队的第 场 比赛 越小 各 队获 1 得的信息越接 近 当然 如果能得到所定义指标 的最优值 从 而可 以衡 量你编 排 的方案是否 达到 了这个最优值 正如本 文 1 6 作的那样 就更 好 了 这个题 目涉及 的是单 循环赛 并且 只有一 块场地 或 同时 只能举 行一 场 比赛 比较 简 单 复 杂一些 的情况有 单循环赛 有多块场地 或 同时可举 行多 场 比赛 双循环赛 即两队 主客场各赛一次 安排赛程 时除间隔场次外 要考虑 主客 场 因素 另 外 像桥 牌 比赛 那样 不 仅对手要轮换 牌局也要 轮换的赛 程安排就更 复杂一些 The M a t h e matic a l Pr o bl e ms f or M a t c h Sc he d ul i n g J I AN G Q i y u a n T s i n g h u a U n i v e r s i t y Be i j i n g 1 0 0 0 8 4 Ab s t r a c t T h e g e n e r a l r e s u l t s f o r th e c o n t e s t t i t l e o f m a t c h s c h e d u l i n g w i th the f o u n d p r o b l e m s i n j u d g i n g s t u d e n ts p a p e r 8 p r e s e n t e d Al s o s o mc p r o b l e ms f o r f u r t h e r s t u d y 8 r e o ffe red Ke y w o r d s ma t c h s c h edu l i n g n u m b e r o f b rea k s b e twe e ntwo a d j a c c n t g a m es o f o n e p l a y e r 上 接 1 3 7页 Op t i m i z ati on De s i g n f or Li n e a l Li g h t Q I A N Z h e n g p i n g C A I R u i c h u S U N H o n g A d v i s o r L I A N G Ma n f a H O N G Y i c h i e f S o u t h C hin a U n i v e rs i t y o f T e c h n o l o g y G u a n g z h o u 5 1 0 6 4 0 A b s t r a c t I n t h i s paper a re fl e c t i o n m ode l f o r l i n e a l li ght i s p r e s e n t ed a n d t h e i n t e n s i t y d i s t r i b u t i o n i s e x a c tl y c al c u l a t