Сначала приведем "оценку", то есть продемонстрируем, что при нечетных n так заполнить таблицу не удастся. Предположим противное и рассмотрим подходящую расстановку чисел. Покрасим таблицу шахматной раскраской так, чтобы клетка в 1-м столбце и 1-й строке оказалась черной; при этом черными окажутся те клетки, сумма номеров строки и столбца которых четна, а белыми – те, у которых эта сумма нечетна. Заметим, что, так как в последовательности от 1 до n² цвета клеток должны чередоваться, числа одной четности должны оказаться в черных клетках, а другой четности – в белых. Рассмотрим клетки таблицы, в которых стоят числа, дающие остаток k при делении на n. Сумма их номеров строк и столбцов, с одной стороны, равна (1 + 2 + 3 + ... + n) + (1 + 2 + 3 + ... + n), так как каждая строка и каждый столбец участвуют по одному разу; в частности, эта сумма четна. С другой стороны, у каждой белой клетки сумма нечетна, что означает, что белых клеток среди рассмотренных должно быть четно (иначе общая сумма была бы нечетна). Наконец, заметим, что при k = 1 среди чисел 1, 1 + n, ..., 1 + nm, ..., 1 + n(n – 1) цвета соответствующих клеток чередуются (соседние числа в этой последовательности имеют разную четность); число белых среди них четно, поэтому число черных нечетно. Однако числа 1 + nm и 2 + nm имеют разные цвета, откуда следует, что при k = 2 среди чисел 2, 2 + n, ..., 2 + nm, ..., 2 + n(n – 1), наоборот, число белых нечетно, что невозможно. Теперь покажем, как заполнить таблицу для четных n. Приведем пример таблицы 8 × 8, заполненной требуемым образом (для наглядности кружочками выделены числа, дающие остаток 5 при делении на 8). Примеры для других четных n строятся аналогично: верхняя строка заполняется числами от 1 до n слева направо, далее правый столбец заполняется следующими числами сверху вниз, следующий столбец (кроме уже занятой верхней клетки) заполняется снизу вверх, и т. д. Докажем, что построенный таким образом пример подходит. Строчки будем нумеровать от 1 до n сверху вниз, а столбцы – справа налево. Ясно, что первое условие (соседние числа находятся в соседних клетках) выполнено. Докажем, что в k-м столбце все числа дают разные остатки от деления на n. Первое число в нем равно k, а до следующего по величине числа t, стоящего в этом столбце (во 2-й или n-й строке), "цепочка" чисел прошла всю правую часть таблицы, то есть ровно n(n – k) клеток. Значит, t = k + 1 + n(n – k) и дает тот же остаток от деления на n, что и k + 1. Получаем, что числа в столбце эквивалентны k, k + 1, k + 2, ..., k + n – 1 при делении на n, то есть дают различные остатки. Теперь рассмотрим строки. Ясно, что в 1-й строке все остатки от деления на n различны. Рассмотрим k-ю строку, k > 1. Воспользуемся тем, что четные и нечетные числа в строке чередуются (как уже было показано в доказательстве оценки, четные и нечетные числа располагаются на клетках разных цветов при шахматной раскраске). При этом четные числа дают четные остатки от деления на n, а нечетные – нечетные остатки (это верно только когда n четно). Также заметим, что последовательные четные числа в строке увеличиваются на 2(n – 1), если идти справа налево, то есть их остатки уменьшаются на 2 (возможно, с переходом через 0); так как всего их n/2, то они как раз дают все различные четные остатки от деления на n. По тем же причинам нечетные числа в рассмотренной строке дают все нечетные остатки. Следовательно, все остатки в строке различны.

При четныхn.