|
|
发表于 2003-8-15 17:43:08
|
显示全部楼层
赛程安排
一 n=2k
左上角不动，逆序旋转法。
例；n=8
1 8
2 7
3 6
4 5
然后保持 1 不动，2345678按逆时针旋转，在同一水平线上的两队进行比赛。
共进行7大轮。
1 7 1 6 1 5 1 4 1 3 1 2
8 6 7 5 6 4 5 3 4 2 3 8
2 5 8 4 7 3 6 2 5 8 4 7
3 4 2 3 8 2 8 7 6 7 5 6
二 n=2k+1 (k>=2)
旋转法
例；n=9
1 9
2 8
3 7
4 6
5 1
9 2
8 3
7 4
6 5
然后保持1不动，上半部分的23456789按顺时针旋转，下半部分的23456789逆 时针旋转，共进行4大轮。
1 2 1 3 1 4
3 9 4 2 5 3
4 8 5 9 6 2
5 7 6 8 7 9
6 1 7 1 8 1
2 3 3 4 4 5
9 4 2 5 3 6
8 5 9 6 2 7
7 6 8 7 9 8
三 奇数方案的数字规律。
（一）符号定义
A(i) 第i支参赛队(1<=i<=n)。
t(ij) Ai队参加的第j场比赛所在的轮数。且规定t(i1)=[(i+1)/2] (1<=i<=n;1<=j<=n-1)。
r(ij) rij=t(ij+1)-t(ij) (1<=i<=n;1<=i<=n-2).
rm(i) rm(i)=min{rij}; (1<=i<=n)。
rm rm=min{rm(i)};
T(i) 赛程时间向量T(i)={t(i1),t(i2),------,t(in-1)};
R(i) 赛程间隔向量R(i)={r(i1),r(i2),------,r(in-2)};
（二）问题分析
引理1 rm<=(n+1)/2
证略.
定理1 rm<=(n-1)/2
证略(提示:用反证法).
引理2 t(ij)=(n+1)/2或t(ij)=(n-1)/2
证略(提示:结合定理1与反证法).
引理3 赛程安排为单循环比赛的充分必要条件是:T(i)℃{1,2,3,------,n*(n-1)/2},∪T(i)={1,2
3,------,n*(n-1)/2},对任意i,j,k有T(i)∩T(j)为单元集且T(i)∩T(j)∩T(k)为空集.
证略.
定理2 满足下列条件的赛程安排即为间隔是(n-3)/2的奇数方案:
当i为奇数且i<n时,R(i)={(n+1)/2,n+1)/2,n+1)/2,------,n+1)/2,(n-1)/2,(n-1)/2,------,(n-1)/2}
其中共有i-1个(n-1)/2,且t(i1)=[(i+1)/2].
当i为偶数时,R(i)={(n-1)/2,(n-1)/2,------,(n-1)/2,(n+1)/2,(n+1)/2,------,(n+1)/2}
其中共有i-1个(n-1)/2,且t(i1)=[(i+1)/2].
当i=n时,R(i)={(n-1)/2,(n+1)/2,(n-1)/2,(n+1)/2,(n-1)/2,------,(n+1)/2,(n-1)/2}
其中(n-1)/2,(n+1)/2交替出现,且t(i1)=[(i+1)/2].
证略(提示:分奇数偶数和n三种情况讨论).
|
|
