Can someone please latex my solution? I can't use latex as I'm a new user Take some station A, k metro lines service it and each has k-1 stations other than A. As every station must be on one of these metro lines, the number of stations is k(k-1)+1. We will say that a metro line goes through S if it connects two stations in S. Take some station A outside of S and assume it's connected to 2 stations in S by the same line. These 2 stations also need to be connected by this line, and therefore A can't be connected to 3 different stations in S by this line, as the three stations will all be connected by the same line. Notice that we can deduce from that that the number of connections from a station outside of S to S using lines that go through S is even, but k is odd so each station has at least one connection to S using a line that doesn't go through S. Now count the number of connections from stations outside of S to stations in S by lines that go through S: there are k choose 2 such lines, each contains k-2 stations outside of S, and every such station is connected by this line to two stations in S. Therefore the number of such connections is 2*(k-2) * (k choose 2) = k(k-1)(k-2). However, the number of total connections from stations outside of S to stations in S is k((k-1)^2+1)=k(k-1)(k-2)+k^2, because there are k(k-1)+1-k=(k-1)^2+1 stations outside of S. Therefore there are exactly k^2 connections from outside of S to S using lines that don't go through S, but every station outside of S has at least one such connections, which gives us at least (k-1)^2+1 such connections. It means that this bound is very tight - it gives 2(k-1) connections to spare, so we will try to exploit it. Notice that we haven't used yet the fact that every two lines intersect (mostly because I forgot that), so now is the time to use it. The current bound gives Denote the stations in S as A_1, A_2,..., A_k. Each of these stations is on k-1 metro lines that go through S, so each one has exactly one metro line that goes through it and doesn't go through S, and all these lines are unique. Denote these lines by M_1, M_2,... M_k. Every two lines have to intersect, and the intersections are always outside of S. We will show that if they don't all intersect on the same station (which means that the intersection satisfies the problem conditions) we would get more than 2(k-1) spare connections from them to S, which will be a contradiction. Notice that every intersection has an odd amount of lines (as there is an even amount of connections between the intersection and S from lines that go through S), so in particular there are no intersections of exactly two lines. An intersection of t lines gives t-1 spare connections, and therefore every intersection gives at least two spare connections. Therefore, if there are more than k-1 intersections we win. There is also no intersection of k-1 lines, as k-1 is even. Take the two maximal intersections X, Y and denote the number of lines in them by x,y respectively. There is at most one line which is in both X and Y, and any pair of lines (one from X and one from Y) must be in a different intersection, so there are at least (x-1)(y-1) intersections. Therefore (x-1)(y-1)<=k-1. Notice that x-1<=(k-1)/2, otherwise we already get a contradiction, and we also get that every other intersection has at most sqrt(k-1) lines. Denote the number of lines in each intersection in descending order by a_1,a_2,...,a_m. we know that sum(a_i-1) <= k-1, and therefore sum(a_i)<=2k, but every pair of lines (M_i, M_j) must be in exactly one intersection, so we have sum(a_i choose 2) = (k-1) choose 2, but as every a_i other than a_1 is less than sqrt(k-1) we get by convexity that: (k-1) choose 2 = sum(a_i choose 2) <= (a_1 choose 2) + sqrt(2k)*(sqrt(2k) choose 2) <= ((k-1)/2 choose 2) + sqrt(2k)*(sqrt(2k) choose 2) which is a contradiction for large k, and you can check small k by hand. Hopefully someone will find a less ugly finish.

This problem is equivalent to the fact that in a finite projective plane of order k-1, where k is an odd integer, if you take an arc of size k it is always contained in an arc of size k+1. This result appears on the Wikipedia page about arcs in projective geometry

Zsigmondy wrote: Can someone please latex my solution? I can't use latex as I'm a new user Sure Btw, the problem is a nice one. Zsigmondy wrote: Take some station $A$, $k$ metro lines service it and each has $k-1$ stations other than $A$. As every station must be on one of these metro lines, the number of stations is $k(k-1)+1$. We will say that a metro line goes through $S$ if it connects two stations in $S$. Take some station $A$ outside of $S$ and assume it's connected to $2$ stations in $S$ by the same line. These $2$ stations also need to be connected by this line, and therefore $A$ can't be connected to $3$ different stations in $S$ by this line, as the three stations will all be connected by the same line. Notice that we can deduce from that that the number of connections from a station outside of $S$ to $S$ using lines that go through $S$ is even, but $k$ is odd so each station has at least one connection to $S$ using a line that doesn't go through $S$. Now count the number of connections from stations outside of $S$ to stations in $S$ by lines that go through $S$: there are $\binom{k}{2}$ such lines, each contains $k-2$ stations outside of S, and every such station is connected by this line to two stations in $S$. Therefore the number of such connections is $2\cdot(k-2) \cdot \binom{k}{2} = k(k-1)(k-2)$. However, the number of total connections from stations outside of $S$ to stations in $S$ is \[k((k-1)^2+1)=k(k-1)(k-2)+k^2,\]because there are $k(k-1)+1-k=(k-1)^2+1$ stations outside of $S$. Therefore there are exactly $k^2$ connections from outside of $S$ to $S$ using lines that don't go through $S$, but every station outside of S has at least one such connections, which gives us at least $(k-1)^2+1$ such connections. It means that this bound is very tight - it gives $2(k-1)$ connections to spare, so we will try to exploit it. Notice that we haven't used yet the fact that every two lines intersect (mostly because I forgot that), so now is the time to use it. The current bound gives Denote the stations in $S$ as $A_1, A_2,..., A_k$. Each of these stations is on $k-1$ metro lines that go through $S$, so each one has exactly one metro line that goes through it and doesn't go through $S$, and all these lines are unique. Denote these lines by $M_1, M_2,\ldots, M_k.$ Every two lines have to intersect, and the intersections are always outside of $S$. We will show that if they don't all intersect on the same station (which means that the intersection satisfies the problem conditions) we would get more than $2(k-1)$ spare connections from them to $S$, which will be a contradiction. Notice that every intersection has an odd amount of lines (as there is an even amount of connections between the intersection and S from lines that go through $S$), so in particular there are no intersections of exactly two lines. An intersection of $t$ lines gives $t-1$ spare connections, and therefore every intersection gives at least two spare connections. Therefore, if there are more than $k-1$ intersections we win. There is also no intersection of $k-1$ lines, as $k-1$ is even. Take the two maximal intersections $X$, $Y$ and denote the number of lines in them by $x,y$ respectively. There is at most one line which is in both $X$ and $Y$, and any pair of lines (one from $X$ and one from $Y$) must be in a different intersection, so there are at least $(x-1)(y-1)$ intersections. Therefore $(x-1)(y-1)\le k-1$. Notice that $x-1\le (k-1)/2$, otherwise we already get a contradiction, and we also get that every other intersection has at most $\sqrt{k-1}$ lines. Denote the number of lines in each intersection in descending order by $a_1,a_2,...,a_m$. we know that $\sum_{i=1}^m (a_i-1) \le k-1$, and therefore $\sum_{i=1}^m a_i\le 2k$, but every pair of lines $(M_i, M_j)$ must be in exactly one intersection, so we have $\sum_{i=1}^m\binom{a_i}2= \binom{k-1}2$, but as every $a_i$ other than $a_1$ is less than $\sqrt{k-1}$ we get by convexity that: \[\binom{k-1}2 = \sum_{i=1}^m\binom{a_i}2\le \binom{a_1}2 + \sqrt{2k}\cdot\binom{\sqrt{2k}}2 \le \binom{(k-1)/2}2 + \sqrt{2k}\cdot\binom{\sqrt{2k}}2,\]which is a contradiction for large $k$, and you can check small $k$ by hand. Hopefully someone will find a less ugly finish. Remark. This problem is equivalent to the fact that in a finite projective plane of order $k-1$, where $k$ is an odd integer, if you take an arc of size $k$ it is always contained in an arc of size $k+1$. This result appears on the Wikipedia page about arcs in projective geometry

@zsigmondy, my proof is similar to yours, so i will leave out the initial steps until just before total number of connections.(i.e until number of connections by lines going through $S$. being $k(k-1)(k-2)$.) The number of total connections however is $k(k-1)^2 = k(k-1)(k-2) + k(k-1)$ as number of stations outside S is $k(k-1)+1 - k = (k-1)^2$ This means that the number of connections so spare we are left with is $k(k-1) - (k-1)^2 = k-1$, a slightly stricter bound which makes things a lot nicer. Now we look at the $k$ lines $M_1, M_2,\ldots, M_k.$ Each of these lines intersect at a station outside of S. an intersection of $t$ lines adds $t-1$ spare connections. We look at line $M_1$, intersections on line $M_1$ add exactly $k-1$ spare points as it meets each line $M_2, \ldots , M_k$ at some point adding a spare connection for each of them. Thus,no more spare connections are left to be formed which implies all intersection points are on $M_1$. However the station at which $M_2$ intersects $M_1$ is unique. Hence all lines $M_3, \ldots, M_k$ must pass intersect both of the aforementioned lines at this unique station. Hence this station is our desired station.

An incredibly beautiful problem/result There are a total of \(k^2 - k + 1\) stations. Since no \(3\) stations are colinear, each line passes through \(0\), \(1\), or \(2\) points in \(S\). We call a line special if it passes through exactly \(1\) point in \(S\). Notice every point in \(S\) is part of exactly \(1\) special line, because all the other \(k-1\) lines it is part of has another member of \(S\) in it. Hence, there are a total of \(k\) special lines. Claim (Parity): Every point outside \(S\) passes through at least one special line. Proof: Summing over all lines passing though the point \(P\), there are a total of \(k\) members of \(S\) (which is odd). Hence there is a line through \(P\) that contains an odd number of members of \(S\), and that odd number must be \(1\). Let \(L_1, L_2, \dots, L_k\) be the \(k\) special lines. Note that each pair of lines intersect at a point, and that \[ \lvert L_1 \cup L_2 \cup \dots \cup L_k \rvert = k^2 - k + 1 \]because every station is part of a special line. We now use the following lemma:

Therefore the maximum value of \( \lvert L_1 \cup L_2 \cup \dots \cup L_k \rvert \) must be achieved: \[ \lvert L_1 \rvert + \lvert L_2 \rvert + \dots + \lvert L_k \rvert - k + 1 = k^2 - k + 1 \]Which means that all the special lines are concurrent. The point of concurrency is the desired station, so we are done.