South-Afrika, 2011

Combinatorics Difficulty 6.6 National Olympiad Prove it South Africa

Let $n$ be a positive integer. A train stops at $2n$ stations, including the first and last ones, numbered in order from the first to the $2n^{th}$ . It is known that on a certain car, for each pair of integers $i, j$ such that $1 \le i < j \le 2n$ , exactly one seat has been reserved for the trip from the $i^{th}$ station to the $j^{th}$ . Find the minimum number of seats that must be available in that car.

Solution

When the train leaves station $k$ , the passengers on board the train are those that are travelling from station $i$ to $j$ , with $i \le k < j$ . Hence there are $k(2n-k)$ people on board the train at that point, with a maximum of $n^2$ between stations $n$ and $n+1$ .

Moreover, at station $k$ there are $k-1$ passengers disembarking, and $2n-k$ passengers boarding, so there needs to be
$(2n - k) - (k - 1) = 2(n - k) + 1$
seats free in the car for $1 \le k \le n$ . After station $n$ , $2(k-n)-1$ seats are left free. So in order for everyone to have a seat up to station $n$ , there needs to be at least $\sum_{k=1}^{n}[2(n-k)+1] = n^2$ seats on the train. Since the number of passengers never exceed $n^2$ , this number will suffice.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.