In the cells of a square table $n$ x $n$ the numbers $1,2,...,n^2$ are written in an arbitrary way. Prove that there exist two adjacent cells, for which the difference between the numbers written in them is no lesser than $n$.
Problem
Source: II International Festival of Young Mathematicians Sozopol 2011, Theme for 10-12 grade
Tags: combinatorics, table, numbers in a table