First of all, let's get rid of the plane shape: we make pairs of columns that have the same "position", so we get n-1 pairs. We put them in ascending order (so we have sometning which looks like a staircase). Doing this, we don't change the fact that each passanger isn't in the same column or row with any other one. Now, we look at the "diagonal" of this shape (bottom-left to up-right). We will prove that it's possible to perform some operations such that all the passengers are in the diagonal without changing the sum. To do this, we will abundantly use this operation: Imagine we have two points with coordinates $(a,b)$ and $(c,d)$. The operation will give us the two points: $(a,d)$ and $(c,b)$ (we just switch their line position without changing their column). Note that the operation is not always possible for any two points since one point may be out of the shape after the operation. Now we prove our claim by induction: Without loss of generality, there's a passenger in the extreme bottom-left place ( $1$ ) and one in the extreme up-right ($ n $) We will fill the diagonal starting from the up-right place, and filling the places going down/left. We use induction: The base case is done Now suppose we have already the k columns in the right with passengers already in the diagonal. This allows us to say that for in the $ k+1$th column (starting from the right), the passenger is : -on the diagonal then it's done -not on the diagonal. Then we can say that it is below the diagonal. Indeed, if it was above it, it would be a contradiction since it would be in the same line as one of the $k$ passengers which are already in the diagonal. We know that there is a passanger who is in the same line as the spot we want to reach (on the diagonal) . We will perform the operation described previously with this passenger and the one who is below the diagonal. We clearly see that the operation is possible and that the passenger is now in the diagonal, completing the induction. So starting from any configuration, we can arrive at the configuration where each passanger is on the diagonal and we know that the sum is the same. Therefore, every configuration has the same sum. The sum is $n^2 - 1$, just alternate the $1$ and $n$ to see this ( $1*(n-1) + n*(n-1) $)