C>Дана квадратная таблица NxN, клетки которой
C>заполнены целыми числами, таким образом, что разность
условие связанности
C>чисел в соседних (имеющих общую грань) клетках равна
C>1, либо 0, либо -1.

C>Доказать, что в таблице присутствует число повторенное
C>не менее N раз.

Лемма 1: В квадрате 2х2 всегда есть минимум 2 одинаковых числа
Попробуем найти такое расположение, чтобы в квадрате не было 2 одинаковых чисел.
Ставим в любую клетку число X. - квадрат симметричен, поэтому, пусть будет левый верхний угол.

X ?
? ?

Очевидно, что больше ни один Х ставить нельзя. 
Тогда рядом с Х можно поставить только +1 или -1.
Два одинаковых числа (++ или --) ставить тоже нельзя, значит, ставим один + и один -
В силу симметричности не важно куда именно
Х -
+ ?
Для выполнения условия "связанности" на оставшееся место можно поставить только Х
Это означает, что в квадрате 2х2 всегда будут минимум два одинаковых числа.

Любой NxN (N > 2 ) квадрат можно разбить на подобласти 2х2 - их будет (N-1)^2
В каждой подобласти должно быть минимум 2 совпадающих числа (по лемме 1),
=> ((N-1)^2) = (N^2 - 2N + 1) = N^2 - 2N + 1 пар одинаковых чисел в квадрате
Всего же чисел N^2

N^2 - (N^2 - 2N + 1) = 2*N - 1 максимум разных чисел во всем квадрате
От противного:
Для того, чтобы одинаковых чисел было менее N 
во всем квадрате должно быть более N^2 - N + 2 разных чисел

Но
(2*N - 1) < (N^2 - N + 2)  или, что то же самое: 0 < N^2 - 3*N + 3, для N >= 2

Противоречие. Значит в любом квадрате есть как минимум N одинаковых чисел.