在 9 城市中设 21 公司，每城至少两个，不同城两公司间要设一线路，问至少要设几条？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

luyuanhong

题  某大公司计划在 9 个城市中设立 21 个分公司，在每一城市中至少要设 2 个

分公司，而且要求在不同城市的任意 2 个分公司之间都必须设置一条通讯线路。

    试问：这 21 个分公司之间最少要设置几条通讯线路？

解  首先，在每个城市至少要设 2 个分公司，9 个城市设 18 个分公司。

    对这 18 个分公司来说，每个分公司与不同城市的其他 16 个分公司之间都要

设置一条通讯线路，所以共要设置 18×16÷2 = 144 条通讯线路（除以 2 是因为

通讯是双向的）。

    还有 3 个分公司，如果分开设立在不同城市，则除了要与其他分公司通讯以外，

这 3 个分公司之间，还要设置通讯线路。为了使得通讯线路数最少，这 3 个分公司

应该设立在同一城市中。这样，3 个分公司每个都只需与不同城市的其他 16 个分公

司之间设置一条通讯线路，共设置 3×16 = 48 条通讯线路。

    所以，这 21 个分公司之间最少要设置 144 + 48 = 192 条通讯线路。