ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66534
Тема:    [ Арифметика остатков (прочее) ]
Сложность: 4
Классы: 7,8,9,10
В корзину
Прислать комментарий

Условие

В клетках квадратной таблицы 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(nk) клеток. Значит, t = k + 1 + n(nk) и дает тот же остаток от деления на 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.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2019
Номер 82
класс
Класс 8
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .