给定整数n > 1 .在一座山上有n2个高度互不相同的缆车车站.有两家缆车公司 A 和B,各运营 k 辆缆车;每辆从一个车站运行到某个更高的车站(中间不停留其他车站) . A 公司的 k 辆缆车的k个起点互不相同, k 个终点也互不相同,并且起点较高的缆车,它的终点也较高. B 公司的缆车也满足相同的条件.我们称两个车站被某家公司连接,如果可以从其中较低的车站通过该公司的一辆或多辆缆车到达较高的车站(中间不允许在车站之间有其他移动).
确定最小的正整数 k ,使得一定有两个车站被两家公司同时连接.
(印度供题)
答案是n2 - n + 1.首先我们说明对 k ≤n2 - n ,存在一种缆车的运行路线,使得不存在两个车站同时被两家公司连接.显然只需对 k = n2 - n,举例,对更小的 k ,从中删去一些缆车即可.设 S1 , S2, … Sn ,是高度依次递增的n2个车站.考虑 A 公司的n2 - n辆缆车,从Si到Si+1,其中 1 ≤ i ≤ n2,且 n|i ; B 公司的n2 - n辆缆车,从Si到Si+1,其中 1 ≤ i ≤ n2 .从而 Si , Sj 被 A 公司连接当且仅当 [i/n] = [j/n] ,被B公司连接当且仅当 i ≡ j (modn),显然这两个条件不能同时成立,故没有两个车站同时被 A 公司和B公司连接.下面证明当 k = n2 - n + 1 时,一定有两个车站被两家公司同时连接.定义有向图 GA , 顶点集为n2个车站{S1,S2, … Sn...
查看完整答案