${N}\times{N}$ chessboard, adjacent squares differ by one Suppose we have ${N}\times{N}$ chessboard such that two squares are adjacent if they share a common side. Populate all squares with integer numbers so that numbers in adjacent squares differ by $1, 0$ or $-1$. Prove that some number appears at least N times.
 A: For any valid $n$ by $n$ grid, let's consider some set $S_k$ that contains any cell whose value is $\leq k$ for some given $k$. If we set $k$ to the maximum value of the cells (call this $m$) in the entire grid, then $S_k$ will contain every cell in the grid (this is our base case). 
We can decrease $k$ to the smallest possible value for which $S_k$ still contains at least one cell from every row or every column. This condition holds for $k=m$, and possibly holds for some $k<m$, but what matters is that this minimal $k$ exists. 
After finding this minimal $k$, let's rotate the grid such that we are looking at a scenario for which $S_k$ (at least) contains a cell from every row.
Let's focus on an arbitrary row. In this row, there exists some cell with value $a$ such that $a \leq k$ (this cell would be in $S_k$ by definition), and there also exists some cell with value $b \geq k$ (since $k$ is minimal across all rows and columns). 
Some more detail on the $b$ cell: Since $k$ is minimal, we know this $b \geq k$ cell always exists. Let's assume it didn't and that every cell in the row had value $k-1$ instead (i.e. something $<k$). Then we could rotate the grid and say that each row (previously column) contains a cell with value $\leq k-1$, which contradicts our condition that $k$ was minimal to begin with. 
Adjacent cells can only differ by at most $1$ in terms of absolute magnitude, which means that in each row there exists some contiguous / horizontal pathway from $a$ to $b$ that must eventually encounter a cell with value $k$.
Since this condition is true for all $n$ rows, we see that $k$ must occur at least $n$ times.
