压轴大题

后面，出题人和主办方总是想再三给华国队使绊子，可惜都被彦清巧妙的化解，甚至还让华国队大出风头。

很快，就到了最后一道题的压轴环节，出题人深吸一口气，看了一眼手中的题目，成不能让华国队失利，就再此一举了。

华国队众人也对视一番，决定还是派彦清上场，毕竟不管怎么说，彦清都是他们四个里面最厉害的一个。

出题人“各位学员请听题，给定整数n>1在一座山上有n2个高度互不相同的缆车车站，有两家缆车公司A和B,各运营k辆缆车；每辆从一个车站运行到某个更高的车站（中间不停留其他车站）。”

出题人“A公司的k辆缆车的k个起点互不相同，k个终点也互不相同，并且起点较高的缆车，它的终点也较高。”

出题人“B公司的缆车也满足相同的条件，我们称两个车站被某家公司连接，如果可以从其中较低的车站通过该公司的一辆或多辆缆车到达较高的车站（中间不允许在车站之间有其他移动）。”

出题人“请确定最小的正整数k，使得一定有两个车站被两家公司同时连接。”

出题人“请各位学员回答，并且完善解答过程，否则答案无效。”

彦清知道这次出题人还是增加了难度，按照往届国际数学竞赛来说，只需要答案，不需要过程，至于愿不愿意说出完整的解答过程，完全是看学员的个人意愿，现在出题人却强制要求完整的过程。

这样的话，且不说学员紧张与否，一旦过程过于复杂，说错一步或者什么的，那么答案也就无效了。

不过彦清没有丝毫的紧张感，她从容地按下抢答按钮，众人的目光和聚光灯都聚集在了彦清的身上，此刻的彦清，在闪闪发亮。

朱彦清小时候“答案是n2-n+1。”

朱彦清小时候“首先我们说明对k≤n2-n，存在一种缆车的运行路线，使得不存在两个车站同时被两家公司连接。”

朱彦清小时候“显然只需对k=n2-n举例，对更小的k，从中删去一些缆车即可。”

朱彦清小时候“设S1,S2,…Sa2是高度依次递增的n2个车站，考虑A公司的n2-n辆缆车，从S;到Si+1,其中1<i<n2，且n|i;B公司的n2-n辆缆车，从S:到S+n，其中1<i<n2-n。”

朱彦清小时候“从而S，S;被A公司连接当且仅当[1=「1，被B公司连接当且仅当i=j(mod n），显然这两个条件不能同时成立，故没有两个车站同时被A公司和B公司连接。”

朱彦清小时候“下面证明当k=n2-n+1时，一定有两个车站被两家公司同时连接。”

朱彦清小时候“定义有向图GA,顶点集为n2个车站{S1,S2,…,Sn2},对于1≤i<j≤n2,当且仅当A公司有一辆缆车从S；运行到S；时，连一条有向边S；→S由条件知，Ga中每个顶点至多一条出边，也至多一条入边，且由于有向边只能从下标较小的顶点指向下标较大的顶点，因此GA也不含有向圈。”

卑微作者解答过程还没完，后面还有，在下一章