Question

有一个非常难的国际数学竞赛题，我一直不明白，有数学大神能帮帮我吗（非常感谢）？

某公司共有 30 名员工，其中有 20 名员工使用 A 品牌的电脑，另外 10 名员工使用 B 品牌的电脑。为了安全起见，电脑之间只能通过电缆连接来传递信息，电缆只能将 A 品牌的电脑和 B 品牌的电脑连接起来。员工的电脑如果通过电缆直接连接起来或者通过多台相连的电脑传递信息，那么员工就可以互相交流。起初，没有任何一台电脑和其他电脑相连，技术员现在开始随机选择两台不同品牌的电脑，在它们之间装上电缆（假设这两台电脑之间没有电缆），直到每个员工都可以互相交流为止。请问技术员最多可能会用到多少根电缆？

Answer 1

方案一：
A1-B1~B10
A2-B1~B10
......
A19-B1~B10
A20-B1
消耗电缆数=10*19+1=191
方案二：
B1-A1~A20
B2-A1~A20
......
B9-A1~A20
B10-A1
消耗电缆数=20*9+1=181
综上所述，技术员最多可能会用到191根电缆

追问

没太懂为什么前面的都是A对10个B，B对20个A，到了A20和B10的时候就只对1个A和1个B了……？🤔能细讲一下吗？

追答

题目要求是问“最多”会用到多少根电缆，那就意味着我们在实现全部A和B互联前，要尽量多的“浪费”电缆，因此：
第一步：任意选取一个A，作为孤岛，这里我们选了A20

第二步：将其余19个A和10个B全互联，要用到190根电缆
第三步：将孤岛与任意一个B互联，就实现了全部电脑的互联
所以最多会用掉191根。
同理，如果第一步任意选取一个B作为孤岛，则最多会用掉181根。
两相比较，最多会用到191根电缆。