Train stops at $n$ stations

Question

This is a problem from a mathematical contest I was unable to answer. I am placing this problem with both the recreational math and calculus tags because I think derivatives are needed. The problem is:

A train stops in all $n$ stations along its route (including the initial and last ones). At each station, a number of passengers equal to the number of stations ahead get on the train, each one going to different stations. If the maximum number of passengers on the train is $420$ , find the number $n$ .

Any idea? I found $n=40$ , approximately, but it was wrong.

Answer 1

At each station, the number of passengers that get off is equal to the number of stations behind that station, and the number of passengers that get on is equal to the number of stations in front of the train. Therefore, clearly, it must be in the middle of the ride that the number of passengers aboard the train is at its largest.

If there are an odd number of stations (including both the end stations), then the maximal number of passengers happens at the stretch to and the stretch from the middle station. If there are an even number of stations, then the maximal number of passengers happens at the stretch between the two middle stations.

So, if there are $N$ stations, and we are at station number $n$ (including the starting station), there are $N-n$ passengers getting on, and $n-1$ passengers getting off. So the total number of passengers on the train as it leaves that station is $$ \sum_{i = 1}^n\Big((N-i) - (i-1)\Big) = \sum_{i = 1}^n\Big(N - 2i + 1\Big)\\ = nN - n(n+1) + n\\ = Nn-n^2 = n(N-n) $$ This has a maximum at $n = N/2$. However, if $N$ is odd, then this is nonsensical in the context of the actual train ride, and we're instead looking for the value at $n = \frac{N-1}2$, or equivalently $n = \frac{N+1}2$. (Station number $\frac{N+1}2$ is the middle station where an equal number of passengers get on as get off, so the number of passengers doesn't change from the station before.)

So, assuming the maximal number of passengers is $420$, what is $N$? Let's first assume that $N$ is even, and see what we get: $$ 420 = N\cdot \frac N2 - \left(\frac N2\right)^2\\ 420 = \frac14N^2\\ \sqrt{1680} = N $$ which doesn't make sense. So let's see what happens if $N$ is odd: $$ 420 = N\cdot \frac{N-1}2 - \left(\frac{N-1}2\right)^2\\ 420 = \frac14N^2-\frac14\\ \sqrt{1681} = N $$ which works out to $N = 41$, which is indeed odd, and everything is fine.

Answer 2

We need to measure how many passengers are on the train on each station. Let $A_k$ be a multiset describing all passengers destinations at station $k$. More precisely, $A_k$ lists all passengers at station $k$; however, instead of giving them different names, we name each passenger with the station to which he is heading.

• On the first station, there are $n-1$ passengers, each heading for one of the remaining $n-1$ stations. We have $A_1 = \{2, 3, \ldots, n\}$.
• On the second one, $1$ passenger leaves (the one that was headed for station $2$) and $n-2$ enter the train (one for each station from $3$ to $n$); so, we have $A_2 = \{3, 3, 4, 4, \ldots, n, n\}$. We conclude there are $2(n-2)$ passengers on the second station.
• The same reasoning applies inductively. On the $k$-th station there will be precisely $k(n-k)$ passengers, since for each of the remaining $n-k$ stations there are $k$ passengers heading to it.

We conclude that at station $k$ there are $k(n-k)$ passengers. We know that the train's capacity is $420$, so for all $k = 1, \ldots, n$ it must hold $$ k(n-k) \le 420. $$ The maximum value of the left hand side is attained when $k = \lfloor \tfrac{n}{2} \rfloor$, and thus all we have to ensure is that $$ \lfloor \tfrac{n}{2} \rfloor (n - \lfloor \tfrac{n}{2} \rfloor) \le 420 $$ For $n = 41$ we get $20 \cdot 21 \le 420$, which is true. Any greater $n$ violates the inequality. So, $n=41$.

Answer 3

If there are $n$ stations on the route, $n-1$ passengers get on or off at each station. The story about how many passengers get off tells us that there is one passenger going from each station to each other station. At the first station $n-1$ passengers get on. At the second station, $1$ passenger gets off and $n-2$ passengers get on and so on. The question does not specify if the passengers getting off do so before or after the passengers getting on. The total number of passengers is $\frac 12n(n-1)$

If $n$ is odd, the maximum number of passengers occurs when the train is at the center station. If the departing passengers get off first, there are $\frac 12(n-1)$ stations behind and $\frac 12(n-1)$ in front, so there will be $\frac 14(n-1)^2$ passengers on the train who do not mount or demount at this station, plus $\frac 12(n-1)$ new or old passengers. This would give $$\frac 14(n-1)^2+\frac 12(n-1)=420$$ which can be solved with $n=41$

Answer 4

Derivatives are not required, nor useful, really. At station $k$, $n-k$ people get on the train, and $k-1$ people get off, so the net increase in passengers is $n-2k+1$. The number of passengers on the strain as it pulls away from station $s$ is $$\sum_{k=1}^s(n-2k+1)=(n+1)s-2\sum_{k=1}^sk=(n+1)s-s(s+1)=s(n-s),$$ and we are told that the maximum value of this is $420.$

When is the maximum achieved? The number of passengers increases so long as $$n-2k+1>0$$ so we see that if the maximum is achieved at station $s$ then$$s=\left\lfloor{n+1\over2}\right\rfloor,$$ and we have to solve $$\left\lfloor{n+1\over2}\right\rfloor\left(n-\left\lfloor{n+1\over2}\right\rfloor\right)=420$$

Can you see how to do this?

Answer 5

The net gain of passengers at successive stations is $n-1,n-3, ...$. Therefore 420 is the sum of the positive numbers in this sequence.

However, the sum of the consecutive odd numbers is a square. Therefore $$420=2+4+ ... +(n-1)$$ and so $n=41$.