ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 66749
УсловиеВ клетках квадратной таблицы n×n, где n > 1, требуется расставить различные целые числа от 1 до n2 так, чтобы каждые два последовательных числа оказались в соседних по стороне клетках, а каждые два числа, дающие одинаковые остатки при делении на n, – в разных строках и в разных столбцах. При каких n это возможно? РешениеПронумеруем столбцы и строки от 1 до n соответственно слева направо и сверху вниз, а также раскрасим доску в шахматном порядке так, чтобы угловая клетка в первом столбце и первой строке была чёрной. Пусть n чётно. Заполним таблицу числами от 1 до n2 так: ставим их друг за другом, начиная от 1, сначала в первой строке слева направо, а потом – вдоль столбцов: вниз по последнему столбцу, вверх по предпоследнему, и т.д. (получается что-то похожее на змейку). В итоге число n2 окажется прямо под 1, см. пример для n = 6 на рисунке. Заменим теперь числа на их остатки по модулю n (см. рисунок). Нетрудно доказать, что они расставлены следующим образом: для нечётного столбца последнее (нижнее) число совпадает с первым числом следующего чётного столбца и вторым числом следующего нечётного. Значит, каждый столбец начинается с остатка i, равного своему номеру, кроме n-го, который начинается с нуля, причём в чётных столбцах остатки идут по возрастанию c i до n−1, а потом с нуля до i−1, а в нечётных – по убыванию с i до 0, а потом с n - 1доi+1. Предположим, что удалось заполнить таблицу при нечётном n. К противоречию можно прийти по-разному. Первый способ. Заметим, что в нашей раскраске чёрными окажутся те клетки, сумма номеров строки и столбца которых чётна, а белыми – остальные. В нашей змейке чисел от 1 до n2 цвета клеток чередуются, поэтому числа одной чётности находятся в чёрных клетках, а другой чётности – в белых. Пусть, например, такая стрелка горизонтальна и ведёт из i-го столбца в (i+1)-й (см.рисунок). В (i+1)-м столбце тоже есть единица. Поскольку у первой стрелки нет пары, вторая стрелка может вести только в (i+2)-й столбец (двойка в (i+1)-м столбце уже занята).
В (i+2)-м столбце тоже есть единица, и стрелка из неё может вести только в (i+3)-й столбец (двойки в (i+1)-м и (i+2)-м столбцах уже заняты). Продолжая, дойдём до единицы в n-м столбце, откуда стрелке идти уже некуда. Противоречие. ОтветПри всех чётных n. ЗамечанияБаллы: 8-9 кл. – 9, 10-11 кл. – 8. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке