2000年美赛B题：蜂窝网络的无线电信道分配

2000年美赛B题：蜂窝网络的无线电信道分配是2000年MCM的B题，英文原题名为Radio Channel Assignments。

发射站与频率编号

在大范围平面上把区域划分为正六边形蜂窝，每个六边形中心设一座发射站。六边形边长记为 $s$ 。频谱被划为等间距信道，依次用正整数1、2、3、……编号，每站分配一个编号。在避免干扰的条件下，远处的发射站可以复用相同信道。

希望所占频谱宽度尽量小。题目把所有可行方案中“使用的最大信道编号”的最小值称为跨度（span）；达到最优跨度的方案不必使用其中每个较小的编号。

原图是由一个中心六边形向外扩展5圈的正六边形蜂窝块，共91个发射站。从左到右有11列，列内六边形数依次是6、7、8、9、10、11、10、9、8、7、6；相邻列上下错开半个中心间距。

为准确说明同一个有限图形，也可用整数对 $(i, j)$ 标注站点：

$| i | \leq 5, | j | \leq 5, | i + j | \leq 5.$

站点在平面的位置可取 $(3 s i / 2, \sqrt{3} s (j + i / 2))$ 。这里仅重述原图点位，未指定任何信道分配。

对原图有限区域，满足以下条件时研究最小跨度：

假设蜂窝格网向各方向无限延伸，重复要求A的研究。

把近距离条件推广为：距离不超过 $2 s$ 的两站，信道编号至少相差给定整数 $k$ ；距离不超过 $4 s$ 的两站仍至少相差1。

分别研究有限图和无限格网的跨度，并给出设计分配方案的有效策略，说明结果怎样随 $k$ 改变。

考虑更多干扰等级、不规则的发射站布局等推广，讨论还应计入哪些因素。另为当地报纸撰写不超过2页的文章，解释研究结果。

COMAP官方原题网页。题号按官方历年矩阵。核对日期：2026年9月22日。