林朝夕知道这次出题人还是增加了难度，按照往届市级数学竞赛来说，只需要答案，不需要过程，至于愿不愿意说出完整的解答过程，完全是看学员的个人意愿，现在出题人却强制要求完整的过程。
这样的话，且不说学员紧张与否，一旦过程过于复杂，说错一步或者什么的，那么答案也就无效了。
不过林朝夕没有丝毫的紧张感，她从容地按下抢答按钮，众人的目光和聚光灯都聚集在了林朝夕的身上，此刻的林朝夕，在闪闪发亮。
芝士世界林朝夕“答案是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也不含有向圈。”
芝士世界林朝夕“已知GA是若干个有相连的并（一个有相连可以只有一个顶点），每个有相连上的两个车站是被A公司连通的。”
芝士世界林朝夕“由于有n2-n+1条边，有n2-n+1个顶点有入边，恰有n-1个顶点没有入边，因此GA有n-1条有相连由抽屉原理，其中有一个有相连至少含有「-]=n+2个顶点，设这个有相连上的顶点集为X，|X|≥n+2.类似定义有相同Gg，同样地，Gg也有n-1条有相连，从而X中有两个顶点Si，S；在GB的同一个有相接上。”
芝士世界林朝夕“于是Si，S；同时被A公司和B公司连接。”
这清晰完美的解答过程不仅折服了众人，也折服了出题人和主办方。
出题人不由自主的朝林朝夕鼓起掌来，眼神中满是欣赏，这次他是真的开始佩服这个八岁的小女孩儿，她折服了自己。
卑微作者麻烦喜欢的这篇文章的小可爱们点赞、打卡、收藏一下，谢谢小可爱们啦！
京公网安备11010502036362号