In Seoul Subway Line 2, subway stations are placed around a circular subway line. Assume that each segment of Seoul Subway Line 2 has a fixed price. Suppose that you hid money at each subway station so that the sum of the money is only enough for one roundtrip around Seoul Subway Line 2.
Prove that there is a station that you can start and take a roundtrip tour of Seoul Subway Line 2 while paying each segment by the money collected at visited stations.
The best solution was submitted by Kang, Dongyub (강동엽), 전산학과 2009학번. Congratulations!
Here is his Solution of Problem 2011-22. (typo in the lemma: replace an+i=an with an+i=ai.)
Alternative solutions were submitted by 서기원 (수리과학과 2009학번, +3 Alternative Solution), 장경석 (2011학번, +3), 김태호 (2011학번, +3), 김범수 (수리과학과 2010학번, +3), 박준하 (하나고등학교 2학년, +3).
loading...
I have another nice solution using the configuration map. Label each weight of vertex and edge as v1, v2, …, vn, e1, e2, …, en by the clockwise order. Next, draw a graph with v-axis and e-axis which end point touch the graph of y=x. I mean this graph is constructed by starting from the origin, go right with measure vi, and go up with measure ei for each i=1, …, n. If the starting graph satisfy the condition that lying under the graph of y=x, then we can finish the roundtrip tour by starting from v1. If it does not, then we can find the uppermost line parallel to the graph of y=x, which touch with our graph. By taking that point as the starting point and translating the front part of graph to the last, we obtain the new graph lying under the graph of y=x, which makes the roundtrip tour possible 🙂