Question 76
Let n be a positive integer. A train stops at 2n stations, including the initial and final stations, numbered in order from 1 to 2n. In a certain carriage, for every pair of integers i,j with $1\le i\lt j\le2n$, exactly one seat has been booked for the journey from station i to station j. Different reservations obviously cannot overlap. Determine, in terms of n, the minimum number of seats that must be available in the carriage for this situation to be possible.