Ладьи сделали ход коня — разбор задачи

Условие

На доске $9 \times 9$ стоят девять ладей: ни две не находятся в одной строке или столбце. Каждую ладью переставили на клетку этой же доски одним ходом шахматного коня. Докажите, что теперь какие-то две ладьи стоят в одной строке или столбце. Если две попали в одну клетку, это тоже считается совпадением.

О задаче · Продвинутый уровень · школьники и взрослые

Тема: Инварианты
Для кого: Продвинутый уровень · школьники и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Пронумеруйте строки и столбцы числами от $1$ до $9$ Сложите номера строк и столбцов всех ладей.

Подсказка 2

Ход коня меняет чётность суммы двух координат. Сколько таких изменений произошло?

Разобрать решение по шагам

Используйте все строки и столбцы

Девять ладей без совпадений на девяти строках занимают каждую строку ровно один раз. То же верно для столбцов. Поэтому сумма всех $18$ координат равна

2(1+2+\cdots+9)=90

и чётна.

Проследите один ход

Конь изменяет одну координату на $1$ другую на $2$ со знаками плюс или минус. Сумма координат меняется на нечётное число и меняет чётность. Девять ходов меняют общую чётность нечётное число раз: итоговая сумма нечётна.

Сравните с предполагаемым результатом

Если после ходов совпадений снова нет, каждая строка и каждый столбец опять заняты ровно один раз. Общая сумма обязана опять равняться $90$ Она не может быть одновременно чётной и нечётной, поэтому совпадение неизбежно.

Сумма координат замечает каждый прыжок

0190сумма координат до ходов

029 измененийкаждый ход меняет чётность

0390 снова?так было бы при отсутствии совпадений

Ответ

Совпадение неизбежно

Главная идея

Инвариант можно искать в сумме координат, даже когда сами положения объектов сильно меняются.

Как заметить эту идею в другой задаче

Конфигурация занимает все строки и столбцы по одному разу, а движение меняет координаты. Сложите координаты: исходная и предполагаемая конечная суммы фиксированы.

Возможная ошибка

Объяснять результат только сменой цвета каждой клетки: нужно ещё доказать, почему новая конфигурация без совпадений противоречит этому.

Источник и примечания

Источник и редакция

А. В. Спивак. «Тысяча и одна задача по математике. 5–7 классы», 2002. С. 81, № 508. Условие пересказано, объяснение и дополнительное упражнение подготовлены для сайта.

Проверь себя

Сохранится ли утверждение для доски $4 \times 4$ и четырёх ладей?

Ответ к дополнительной задаче

Нет. Возьмите ладьи в клетках $(1,1)$ $(2,2)$ $(3,3)$ $(4,4)$ и переставьте соответственно в $(2,3)$ $(4,1)$ $(1,4)$ $(3,2)$ Все четыре перемещения — ходы коня, а новые строки и столбцы по-прежнему различны.

Продолжить тему: Чётность →

Тема, знания и приёмы

Чётность · Нужна школьная база

Ходы коня и ладьи
Чётные и нечётные числа

Приёмы решения: Инвариант или монотонная величина

Задать вопрос по задаче →

Условие

Используйте все строки и столбцы

Проследите один ход

Сравните с предполагаемым результатом

Источник и редакция

Условие

Дополнительная задача