《高教社杯全国大学生数学建模竞赛(大专组)D题赛程安排 参考答案》由会员分享，可在线阅读，更多相关《高教社杯全国大学生数学建模竞赛(大专组)D题赛程安排 参考答案（3页珍藏版）》请在金锄头文库上搜索。
1、20022002 高教社杯全国大学生数学建模竞赛（大专组）高教社杯全国大学生数学建模竞赛（大专组）D D 题题赛程安排赛程安排 参考答案参考答案注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。1)多种方法 (甚至凑的方法) 都能给出一个达到要求的赛程, 如表 1.表 1ABCDE每两场比赛间相隔场次数AX16931, 2, 2B1X47102, 2, 2C64X281, 1, 1D972X52, 1, 1E31085X1, 2, 12)当 n 支球队比赛时, 各队每两场比赛中间相隔的场次数的上限r .证明2如下:1.设n为奇数, n = 2k +
2、 1. 共比赛N = k(2k + 1)场. 考察前k + 1场, 有2k +2个队参赛, 于是至少有 1 个队两次参赛, 这个队在这两场比赛间相隔场次数 r 不超过(k 1)11 k 1.22.设 n 为偶数, n = 2k. 共比赛 N = k(2k - 1)场. 同上, 在前 k + 1 场中至少有 1 个队(记这样的一个队为 A)两次参赛, 记 A 第 j 场比赛在赛程中是第 aj场, 于是n3n 3a11, a2 k 1.若a2 k 1, 则r a2 a11 k 2 ;2若a2 k 1, 但a11, 同样有r a2 a11 k 2 ;2若a11, a2 k 1, 在前 k + 1 场
3、中除 A 外有 2k 个队参赛, 于是至少又有1 个队(记这样的一个队为 B)两次参赛, 记 B 第 j 场比赛在赛程中是第 bj场,则必有n 3n 3b11, b2 k 1, 或b11, b2 k 1(即不可能b11, b2 k 1), 故n 3.r b2b11 k 2 23)n=8, 相隔场次数的上限为 r=2. 记 8 支球队为 1,2, 8, 共 28 场比赛. 一种编制赛程的办法是将赛程分为 7 轮, 每轮 4 场, 各队在每轮中相遇, 具体如下:1.构造M1 2场 7 对 8.1357 为第 1 轮, 即第 1 场 1 对 2, 第 2 场 3 对 4, , 第 44681578
4、为第2轮, 方法是: M1的1不动, 其余7个数字按逆2462.构造M2 3时针转动, 换一个位置.3.依此构造 M3, M7, 将 M1, M7接起来, 就得到整个赛程 M:13571578178618M 246832465324756416421423123532875368754687即第 1 场 1 对 2, 第 2 场 3 对 4, , 第 28 场 5 对 7.4.容易得到赛程 M 各队每两场比赛中间相隔的场次数及其总数, 如表 2.表 2队相隔的场次数相隔场次总数13, 3, 3, 3, 3, 31824, 4, 4, 3, 2, 21932, 4, 4, 4, 3, 21944
5、, 4, 3, 2, 2, 21752, 2, 4, 4, 4, 31964, 3, 2, 2, 2, 41772, 2, 2, 4, 4, 41883, 2, 2, 2, 4, 417以上方法可以推广用于 n 为偶数的情况.n=9, 相隔场次数的上限为r=3. 记 9 支球队为 1,2, 9, 共 36 场比赛. 一种编制赛程的办法是1.画一 49 的表格, 如表 3. 第 i 行第 j列的格子记作(i,j), 在每格左侧先按行依次填 1, 3, 5, 7 ( 第 1 行 1 个 1, 第 2 行 3 个 3, , 第 4 行 7 个 7), 后按行依次填8, 6, 4, 2 , 构成每场比
6、赛的第 1 支队.表 3.1 12 23 34 45 56 67 78 89 91 11888888882 23336666663 35555544444 47777777222.在格的右侧沿各对角线填1, 3, 5, 7, 如表 4: 自(2,2)至(4,4), 跳过一列再自(1,6)至(4,9)填 1, 使 1 的总数(包括格子左侧的)为 8, 自(3,4)至(4,5), 跳过一列再自(1,7)至(3,9)填 3, 使 3 的总数(包括格子左侧的)为 8, .表 41 12 23 34 45 56 67 78 89 91 11888881 83 85 872 2331 366661 63
7、653 35551 53 54441 434 477771 73 75 72213.在格的右侧沿各对角线填 2, 4, 6, 方法与上类似. 最后在未满的 8 个格中填 9,得到表 5. 按照表 5 先列后行的顺序排列得到赛程M*, 即第 1 场 1 对 9, 第 2 场3 对 2, , 第 36 场 2 对 1.表 51 12 23 34 45 56 67 78 89 91 119 89 86 84 82 81 83 85 872 232 31 39 69 64 62 61 63 653 354 52 51 53 59 49 42 41 434 476 74 72 71 73 75 79 2
8、9 214. 容易得到赛程 M*各队每两场比赛中间相隔的场次数及其总数, 如表 6.表 6队相隔的场次数相隔场次总数14, 4, 4, 4, 4, 4, 42824, 4, 4, 4, 4, 4,32733, 3, 4, 4, 4, 4, 42644, 4, 4, 4, 3,3, 32553, 3, 3, 3, 4, 4, 42464, 4, 3, 3, 3, 3, 32373, 3, 3, 3, 3, 3, 42283, 3, 3, 3, 3, 3, 32193, 4, 3, 4, 3, 4, 324以上方法可以推广用于 n 为奇数的情况.4)除每两场比赛间相隔场次数外, 还可给出以下指标:
9、1.平均相隔场次数.记第 i队第 j个间隔场次数为cij, i=1,2,.,n, j=1,2,.,n-2, 则平均相隔场次nn21数为r cij,r是赛程整体意义下的指标, 它越大越好.n(n 2)i1 j1检查 n=8 的赛程 M, 得r=3; n=9 的赛程 M*, 得r=220/63=3.49.实际上, 可以得到r的上限:rmax2k2k 4k21,n 2k 1, 上述,n 2kk 1结果表明,赛程 M 和 M*都已达到了这个上限.2.相隔场次的最大偏差.定义f maxcij r为总体最大偏差 ,g maxi. jicj1n2ij(n2)r为球队最大偏差, 它们都越小越好.检查 n=8 的赛程 M, 得 f=1, g=1; n=9 的赛程 M*, 得 f=0.5, g=5.5.实际上, 可以得到 f 的下限:fmin 2k24k21,n 2k 1,以及 n=2k,n 2k1时 g 的下限:gmin1.结果表明,赛程 M 达到了 f 和 g 下限,M*也达到了 f 的下限.
