Про хромую ладью и домино

Должно быть, вы сейчас прочитали заголовок и задумались: при чем тут домино, если ладья – это шахматная фигура? Да еще и хромая! Все мы знаем, что шахматные фигуры ходят по-разному, но, казалось бы, их возможности хода давно прописаны в правилах. У нас с вами получается очень странная игра!

Разумеется, здесь не обошлось без математиков. Еще в 70-х годах прошлого века при механико-математическом факультете МГУ работали математические кружки для школьников 7-10 классов. В то время они назывались «Школа Юного Математика», а сейчас носят гордое звание Малого Мехмата. Специально для этой школы профессорами университета составлялась программа обучения и, конечно, придумывались задачи. Неизвестно, кому первому пришла голову идея использовать в задаче «исполнителя», который может делать ход ровно на одну клетку по горизонтали или вертикали, но такая схема оказалась неожиданно удобной для описания многих математических процессов – и, конечно, прижилась в задачах. В какой-то момент этому исполнителю потребовалось имя, а «хромая ладья» оказалось самым «говорящим» вариантом. Сегодня встретить хромую ладью можно во многих олимпиадных задачах. Что ж, будем знакомы!

Осталось еще кое-что, что мы не объяснили – домино! В этот раз математики превзошли сами себя, и в задаче будут одновременно использоваться сразу два игровых набора – что только не сделаешь ради науки? По условию, клетки шахматной доски должны быть того же размера, что и половина доминошки, то есть, доминошка имеет размер 2×1. А вот размеры шахматной доски у нас с вами опять неклассические: 2N×2N, и число N нам с вами неизвестно. Вся шахматная доска покрыта неперекрывающимися доминошками. Теперь наше игровое поле готово!

В задаче всего одно действующее лицо, и это, как вы уже догадались, хромая ладья. Она проходит по шахматной доске, посетив каждую клетку ровно один раз. При этом ход, сделанный вдоль одной доминошки, то есть с одной клетки, которую она закрывает, на другую, мы назовем продольным. Настало время вопросов! Каково же наибольшее и наименьшее число продольных ходов?

Давайте начнем с оценки сверху. Каждую клетку хромая ладья посещает ровно один раз, а значит, по одной доминошке может сделать только один продольный ход. Таким образом, возможный максимум – количество доминошек, равное числу клеток доски, деленному на два:  Осталось выяснить, достигается ли этот максимум? Приведем пример! Пусть хромая ладья прошла произвольный путь по доске – пронумеруем все посещенные ею клетки от 1 до  . А теперь разложим доминошки на каждую (2k – 1)-ю и (2k)-ю клетки. Готово, случай  продольных ходов найден!
С минимальной оценкой все немного интереснее. Разумеется, возможный минимум – 0 продольных шагов, но он не достигается даже для N = 1. Посмотрите сами:

Хотя бы один продольный ход придется сделать в любом случае.

Теперь подумаем над случаем N ≥ 2. В каком положении хромой ладье придется сделать ход в строго определенном направлении? Когда больше идти некуда, не так ли? Такая ситуация возникает в углу шахматной доски: угловая клетка имеет всего две соседних, поэтому, если из одной из них ладья пришла, то на вторую вынуждена будет наступить следующей. А так как в углу доминошка может располагаться только теми же двумя способами, то один из этих ходов обязательно будет продольным.

У шахматной доски 4 угла, однако в одном из них хромая ладья может начать свой путь, а во втором – закончить. Остается хотя бы два угла, в которых придется делать продольные ходы.

Итак, найденный нами минимум – 2 продольных хода. Осталось выяснить, достигается ди он для любого N ≥ 2? Нужно привести пример!

Давайте положим две доминошки вертикально в два верхних угла доски, а все оставшиеся – горизонтально. Пусть ладья пройдет по доске змейкой из нижнего левого угла в правый нижний угол. Для любого N таким способом мы получим всего два продольных хода – только в вертикальных доминошках.

Итак, мы нашли и максимум, и минимум продольных ходов хромой ладьи. Наша необычная задача с двумя играми решена!