Solution:

Let us consider the stretch from the $n$-th station to the $n+1$-th one. On this stretch, in the carriage in question, there are all the passengers who boarded at one of the $n$ stations from the first to the $n$-th one and are heading to one of the $n$ stations from the $n+1$-th to the $2 n$-th one. The total number of passengers present at that moment in that carriage is then the product of the number of preceding stations by the number of following stations, that is $n^{2}$, which is then the minimum number of seats that must be available.

Furthermore, $n^{2}$ seats are also sufficient. Indeed, let us place the bookings in the following way:
- $2 n-1$ seats occupied for the whole route of the train, of which 1 occupied by the passenger traveling from the first to the $2 n$-th station and the other $2 n-2$, for every integer $k$ such that $1<k<2 n$, occupied first by the passenger traveling from the first to the $k$-th station and then by the passenger traveling from the $k$-th to the $2 n$-th station.
- $2 n-3$ seats occupied from the second to the $2 n - 1$-th station, of which 1 occupied by the passenger traveling from the second to the $2 n - 1$-th station and the other $2 n-4$, for every integer $k$ such that $2<k<2 n-2$, occupied first by the passenger traveling from the second to the $k$-th station and then by the passenger traveling from the $k$-th to the $2 n - 1$-th station.
- ...
- 3 seats occupied from the $n - 1$-th to the $n+2$-th station, of which one for the journey between stations $n-1$ and $n+2$, one for the journey between stations $n-1$ and $n$ and then between $n$ and $n+2$, and the last one first for the journey between $n-1$ and $n+1$ and afterward for the journey between $n+1$ and $n+2$.
- 1 seat for the journey between station $n$ and $n+1$
In this way the seats needed are given by the sum of all the odd integers from 1 to $2 n-1$, and they are $n^{2}$ by a well-known identity. Let $i, j$ then be integers such that $1 \leq i<j \leq 2 n$. Then:
- If $i<j \leq n$ the passenger traveling between the $i$-th and the $j$-th station will have one of the $2 n-2 i+1$ seats occupied for the journey between the $i$-th station and the $2 n+1-i$-th one, and symmetrically if $n+1 \leq i<j$.
- If $i \leq n$ and $n+1 \leq j$, and $n-i>j-(n+1)$, the passenger traveling between the $i$-th and the $j$-th station will have one of the $2 n-2 i+1$ seats occupied for the journey between the $i$-th station and the $2 n+1-i$-th one, and symmetrically if $n-i<j-(n+1)$. If instead $n-i=j-(n+1)$ the journey will take place entirely on one of the seats occupied between the $i$-th station and the $2 n+1 - i$-th one. There are no other cases for the choice of $i$ and $j$, so all the necessary seats have been assigned to their respective passengers.

- For $n=1$ it is clearly sufficient to have $1=1^{2}$ seat to go from the first to the second station.
- If $n>1$, for the passengers traveling between the $i$-th and the $j$-th station with $1<i<j<2 n$, $(n-1)^{2}$ seats are sufficient; indeed we can apply the inductive hypothesis to the stretch from the second to the $2 n - 1$-th station, which contains $2(n-1)$ stations. Moreover there are added 1 passenger traveling between the first and the $2 n$-th station, who will require a further seat, $2 n-2$ passengers traveling between the first and the $k$-th station, with $1<k<2 n$, and another $2 n-2$ traveling between the $h$-th and the $2 n-2$-th station, for $1<h<2 n$; these latter ones can be arranged in $2 n-2$ seats by having, for every integer $k$ such that $1<k<2 n$, one seat occupied first by the passenger traveling between the first and the $k$-th station and then by the passenger traveling from the $k$-th station to the end. It will then be enough to add $2 n-1$ seats, and $(n-1)^{2}+2 n-1=n^{2}$

Let us show that, if there are at least $n^{2}$ total seats available, at any station other than obviously the final one, regardless of how the passengers sit down when boarding the train and then occupy the seat for the whole duration of their respective journey, the newly boarding passengers will always find a free seat for themselves.
At the $k$-th station, with $1 \leq k<2 n$, at the moment the new passengers board the train, there are still in the carriage all the passengers traveling starting from one of the stations preceding the $k$-th one and heading to one of the stations following it, and there are therefore $(k-1)(2 n-k)$ of them. There remain available $n^{2}-(k-1)(2 n-k)$ seats, which must be enough for the $2 n-k$ passengers who are boarding at the $k$-th station. It must therefore hold that $n^{2}-(k-1)(2 n-k) \geq 2 n-k$, that is $n^{2} \geq(k-1)(2 n-k)+2 n-k=k(2 n-k)=(n-(n-k))(n+(n-k))=n^{2}-(n-k)^{2}$, and this is indeed the case, since $(n-k)^{2} \geq 0$ being a square.