The positive integers from 1 to $n^2$ are placed arbitrarily on the $n^2$ squares of a $n\times n$ chessboard. Two squares are called adjacent if they have a common side. Show that two opposite corner squares can be joined by a path of $2n-1$ adjacent squares so that the sum of the numbers placed on them is at least $\left\lfloor \frac{n^3} 2 \right\rfloor + n^2 - n + 1$. Radu Gologan
Problem
Source: Romanian JBMO TST, Day 4, Problem 13
Tags: floor function, combinatorics proposed, combinatorics