|
|
 |
Условие
В клетках квадратной таблицы n × n, где n > 1, требуется расставить различные целые числа от 1 до n2 так,
чтобы каждые два последовательных числа оказались в соседних по стороне клетках, а каждые два числа, дающие
одинаковые остатки при делении на n, – в разных строках
и в разных столбцах. При каких n это возможно?
Решение
Сначала приведем "оценку", то есть продемонстрируем, что при нечетных n так заполнить таблицу не удастся. Предположим противное и рассмотрим подходящую расстановку чисел. Покрасим таблицу шахматной раскраской так, чтобы клетка в 1-м столбце и 1-й строке оказалась черной; при этом черными окажутся те клетки, сумма номеров строки и столбца которых четна, а белыми – те, у которых эта сумма нечетна. Заметим, что, так как в последовательности от 1 до n2 цвета клеток должны чередоваться, числа одной четности должны оказаться в черных клетках, а другой четности – в белых.
Рассмотрим клетки таблицы, в которых стоят числа, дающие остаток 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. По
тем же причинам нечетные числа в рассмотренной строке
дают все нечетные остатки. Следовательно, все остатки в
строке различны.
