Клетчатые задачи

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

Оценка. Окрасим в белый (черный) цвет клетки, в которых диагонали проведены как в левой верхней (правой нижней) клетке. Задача свелась к поиску количества пар соседних одноцветных клеток. Пройдем от белой клетки к черной клетке по верхней строке и правому столбцу. Всего на этом пути нечетное число клеток, поэтому чередоваться по цвету они не могут. Значит, найдется пара одноцветных соседей. Такая же пара найдется на втором пути (по левому столбцу и нижней строке), соединяющем эти две клетки. Аналогично соединим двумя путями клетки и и и На каждом таком пути будет пара одноцветных соседей и все эти пар разные.

Пример. На рисунке приведена раскраска доски где есть ровно пар одноцветных соседей. Раскраска доски строится аналогично (сначала красим все клетки в шахматном порядке, а потом в правом нижнем квадрате заменяем цвета всех клеток на противоположные).

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

Построим пример для и ходов (для тогда тоже получится). Произвольный квадрат разбиваем на квадратов и к каждому раза применяем операцию прибавления В любом квадрате числа в вершинах на превосходят поэтому сумма их не превосходит 896.

Пусть в таблице строк и столбцов, а клетка, получившая одинаковые номера, расположена в строке с номером и в столбце с номером Тогда, если считать по строкам, в этой клетке стоит число а если считать по столбцам, то это Следовательно, что равносильно

Если или то номера Пети и Васи совпадут во всех клетках. Значит, и Пусть тогда где Получаем Поэтому так как аналогично с Следовательно, количество клеток, получивших одинаковые номера, равно

Так как то или, наоборот, (чтобы убедиться, что других вариантов нет, достаточно перебрать остатки по модулю 4). В любом случае,

Мы покажем, что (i) если то любая хорошая расстановка содержат пустой квадрат но (ii) если то существует хорошая расстановка, которая его не содержит.

(i). Предположим, что Рассмотрим произвольную хорошую счастливую расстановку. Существует ряд в крайнем левом поле которого стоит ладья. Рассмотрим последовательных строк, одной из которых является Их объединение содержит ровно ладей.Теперь удалите крайние левые столбцы из (таким образом будет удалена хотя бы одна ладья). Оставшаяся часть представляет собой прямоугольник поэтому его можно разбить на квадраты размером и эта часть содержит не более ладьи. Таким образом, один из этих квадратов пуст.

(ii). Теперь предположим, что Сначала мы построим хорошую расстановку без пустого квадрата для случая После этого мы изменим его, чтобы он работал при меньших значениях

Пронумеруем строки снизу вверх, а столбцы слева направо числами Каждое поле доски будем обозначать, как обычно, парой номеров его строки и столбца. Теперь расставим ладьи на всех полях вида где (на рисунке ниже показано расположение для ). Поскольку каждое число от 0 до имеет уникальное представление вида каждая строка и каждый столбец содержат ровно одну ладью.

Далее, мы покажем, что в каждом квадрате на доске есть ладья. Рассмотрим такой квадрат и рассмотрим последовательных строк, объединение которых содержит Пусть самая нижняя из этих строк имеет номер с (обратите внимание, что ). Тогда ладьи в этом союзе расставляются по столбцам с номерами

или, расположив эти числа в порядке возрастания,

Легко проверить, что первое число в этом списке не превосходит (если то а первое число в списке — ), последнее не превышает а разница между любыми двумя последовательными числами не превышает Таким образом, один из последовательных столбцов, пересекающих содержит число, указанное выше, и ладья в этом столбце находится внутри что и требовалось. Конструкция для установлена.

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

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

С другой стороны, покажем, что меньше, чем ладей, может и не хватить. Для этого пронумеруем клетки так, чтобы клетки одной диагонали были пронумерованы (остальные клетки нумеруем произвольно). Тогда одна ладья не сможет побывать на двух клетках этой диагонали: если ладья встала на одну из этих клеток, то следующим ходом она обязана будет пойти на клетку с номером, большим и значит, после этого она не сможет вернуться на диагональ.

Наконец, поскольку на каждой клетке диагонали должна побывать ладья, Пете придётся использовать не менее ладей.

Рассмотрим расстояния между выбранными клетками в каждой строке. Они могут принимать значения При этом если в строке клеток, то различных расстояний в ней хотя бы (от крайней клетки до всех). Если в каких-то двух строчках нашлись два равных расстояния, то точки образуют параллелограмм, потому такого быть не может. Отсюда каждое расстояние встречается не более одного раза (рассматривая только различных из каждой строки). То есть — сумма числа расстояний по всем строкам и Осталось привести пример. Для этого выберем все клетки на большой диагонали и на любой из смежных с ней сторон.

Пример. Закрасим все клетки одной строки и все клетки одного столбца, за исключением их общей клетки. В этом случае условие задачи выполнено и закрашено ровно клеток.

Оценка. Для каждой закрашенной клетки выделим ту линию (строку или столбец), в которой она единственная закрашенная. При этом не может быть выделено больше строк. Действительно, если выделено строк, то каждая закрашенная клетка — единственная именно в своей строке, но тогда закрашенных клеток — не более Аналогично не может быть выделено и больше столбцов. Поэтому выделенных линий не больше а значит, и закрашенных клеток, не более чем

Оценка. Из каждого мамонта выпустим три стрелки в тех направлениях, в которых он бьёт. Сопоставим стрелку диагонали (не обязательно главной), если мамонт, из которого ведёт стрелка, стоит в этой диагонали, а стрелка идёт вдоль неё. Тогда каждой диагонали сопоставлено не более двух стрелок: в противном случае две из них будут идти в одном направлении, и один из мамонтов будет бить другого. Поскольку диагоналей всего (по в каждом направлении), стрелок им сопоставлено не более а значит, всего мамонтов не больше

Пример. Три возможных примера расположения мамонтов, не бьющих друг друга, показаны на рисунке.

Ладья бьёт всего клеток — в своей вертикали и своей горизонтали. Рассмотрим другую клетку C в этой горизонтали. Её бьёт еще ровно одна ладья находящаяся с ней в одной вертикали. Эта же ладья бьёт одну клетку находящуюся с в одной вертикали. — угловые клетки клетчатого прямоугольника. Если этот прямоугольник — квадрат, ладьям и достанется по половине от клеток и Если же он — не квадрат, то одна из клеток и достанется ладье а другая — ладье Отсюда ясно, что ладье всего достанется клеток: та, на которой она стоит, и половина от оставшихся клеток. То же верно для каждой ладьи.

Оценка. Пронумеруем строки и столбцы числами от до Покрасим клетки доски в четыре цвета и следующим образом: клетки вида при некоторых натуральных и — в цвет , — в цвет — в цвет и — в цвет

Из клетки цвета ладья должна перейти в клетку цвета или В первом случае порядок цветов посещенных ячеек задается во втором случае это Поскольку маршрут замкнут, он должен содержать одинаковое количество клеток каждого цвета. Существует всего клеток цвета Далее мы покажем, что ладья не может посетить все клетки цвета на своем маршруте и, следовательно, максимально возможное количество клеток в маршруте равно

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

Пусть ладья пройдет следующий путь

Без ограничения общности клетка покрашена в цвет (иначе поменяем роли столбцов и строк).

Теперь рассмотрим клетку Единственный путь, которым ладья может пройти через него — через именно в этом порядке, поскольку согласно нашему предположение, после каждой клетки цвета ладья проходит через клетку цвета . Следовательно, чтобы соединить эти две части пути, должно быть путь, соединяющий ячейки и а также путь, соединяющий и Но эти четыре клетки являются противоположными вершинами выпуклого четырехугольника, а пути находятся вне этого четырехугольника и, следовательно, должны пересекаться. Это связано со следующим фактом: Путь от до вместе с отрезком, соединяющим эти две ячейки, образуют замкнутый контур, в котором есть одна из ячеек и внутри, а другой снаружи. Таким образом, путь между этими двумя точками должен пересекать предыдущий путь.

Но пересечение возможно только в том случае, если ячейка посещена дважды. Это противоречие. Следовательно, количество посещенных ячеек не превышает

Пример. На рисунке показана рекурсивная конструкция для всех -шахматных досок, где имеет вид при некотором натуральном которая дает путь, не содержащий ровно одну клетку цвета (отмеченную точкой, центральную ячейку -шахматная доска) и, следовательно, в случае проходит ровно через клеток.

Над (под) диагональю находится чисел. Заметим, что сумма 300 наибольших чисел таблицы (14, 15, , 25, взятые по 25 раз) равна и ровно в три раза больше суммы 300 наименьших чисел (1, 2, …, 12, взятые по 25 раз), которая равна . Обозначим . Тогда если над диагональю есть число меньше 14, то там сумма меньше, чем , а под диагональю всегда хотя бы ?! Значит, над диагональю все максимальные числа и аналогично под диагональю все минимальные числа. Тогда все числа на диагонали равны 13.

Клетки, не лежащие на краю доски образуют квадрат Разобьем его на квадраты В каждом из них стоит не более одного короля, то есть всего королей во внутренних клетках доски — не более Поэтому на краю доски стоят не менее королей. Теперь разобьем на квадраты всю доску и поставим по королю в левую верхнюю клетку каждого из них. Получим королей, не бьющих друг друга, из которых на краю стоят ровно

Предположим, что на поле можно разместить фигуры при , тогда можно разместить и при . Разобьём поле на 16 квадратов , тогда ровно в 12 из них будут стоять по 1 королю («к»), а в 4 других - 12 коней-лошадей («л») и 1 мяч, т.е. 13 фигур, значит, пустых квадратов быть не должно. Соответственно, квадраты будем называть к-квадраты и л-квадраты. Заметим, что если хотя бы в одном из л-квадратов две «л» стоят у общей стороны с другим квадратом, то этот соседний квадрат не будет содержать «к», значит, он должен быть л-квадратом, но тогда в сумме в этих двух квадратах разместится не более 4 фигур, т.к. клетки прямоугольника разбиваются на пары в виде хода «л», а во всех 4 л-квадратах разместится не более фигур, а должно быть 13. Кроме того, не существует л-квадратов с 4 «л» (аналогичные рассуждения). Значит, в каждом л-квадрате будет ровно 3 «л» и никакие 2 «л» не могут стоять парой у общей стороны с другим квадратом, следовательно, такие л-квадраты находятся в углах поля и 3 «л» стоят с краю всего поля, причём в одном из них ещё стоит и мяч.

Тогда из двух выделенных на поле квадратов хотя бы один должен оказаться пустым противоречие. Значит, .

Для уже можно построить пример. Отметим слоном мяч и поставим королей и коней.

Покрасим клетки каждой грани куба в шахматном порядке так, чтобы угловые клетки были чёрными. При этом каждая грань содержит чёрную и белых клеток. Заметим, что все согнутые полоски будут одноцветными, а все остальные — нет. Так как количество чёрных клеток на больше чем количество белых, то число чёрных согнутых полосок на больше чем число белых. Следовательно, эти числа разной чётности, и их сумма нечётна.

Ясно, что ломаная пересекает диагональ. Пусть — одна из вершин ломаной, лежащая на диагонали. Будем двигаться по ломаной, пока не попадём в первый раз снова в вершину лежащую на диагонали. Из симметрии, если двигаться по ломаной из в другую сторону, то также окажется первой вершиной на диагонали, в которую мы попадём. При этом ломаная уже замкнётся, поэтому через остальные центров клеток на диагонали ломаная не проходит.

Раскрасим доску в шахматном порядке так, чтобы диагональ была чёрной. Заметим, что на нашей ломаной белые и чёрные клетки чередуются, поэтому их количества равны. Всего на доске чёрных клеток. Поскольку клетки диагонали чёрные и ломаная не проходит через из них, то она проходит не более чем через чёрных клеток. Итого длина ломаной не более

Пусть в верхней строке стоят числа Можно считать, что стоит в ом столбце и (этого можно достигнуть перестановкой столбцов). Тогда в нижней строке соответственно стоят числа Легко видеть, что Если то можно вычеркнуть все числа нижней строки. В противном случае найдем наименьшее такое что Вычеркнем из верхней строки все числа а из нижней — числа Тогда имеем

Заметим, что (в силу выбора Тогда

Заметим, что

Предположим, что существует такая расстановка чисел, что оба червяка доберутся до противоположного углового кубика. Пусть числа, стоящие в начальном и конечном угловых кубиках равны и соответственно. Можно считать, что Заметим, что числа и отличаются по крайней мере на так как второй червяк сделал хотя бы ходов (как минимум по в каждом из трех направлений). Также можно считать, что каждый червяк не заползает в каждый кубик больше одного раза (иначе путь от этого кубика до него же можно опустить). Тогда первый червяк должен последовательно проползти через кубики с числами Второй должен последовательно проползти через кубики с числами Рассмотрим теперь шахматную раскраску нашего куба. Можно считать, что кубик с числом покрашен в черный цвет. Заметим, что соседние по грани кубики должны иметь разные цвета. Это означает, что кубики с числами должны быть покрашены в черный цвет (следует из пути -ого червы), а кубики должны быть покрашены в белый цвет (следует из пути -ого червя). То есть кубик с числом должен быть покрашен и в черный, и в белый цвета. Полученное противоречие завершает доказательство.

Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть — ое число первой строки. Рассмотрим сумму

Докажем, что Пусть е слагаемое этой суммы равно Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что то есть Пусть то есть Тогда в первых столбцах содержатся только числа от до следовательно, там содержатся все такие числа. Отсюда следует, что и Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых. Итак,

Это число достигается для таблицы, в которой первые три клетки первой строки заполнены единицами, а дальше идут числа Далее заполняем столбцы: в первом столбце все единицы, кроме последних двух ячеек, заполненных двойками. Во втором столбце после первой единицы стоят двойки во всех ячейках, кроме последних двух, заполненных тройками. После этого все столбцы, кроме последнего, заполняются по принципу: пусть в первой ячейке этого столбца стоит тогда во всех остальных ячейках, кроме двух последних ставится а в двух последних — В последнем столбце 8 последних ячеек заполняются числом

Сначала оценим наименьшее число ходов. Чтобы попасть на противоположную сторону доски, фишке надо сделать семь вертикальных ходов. Но хотя бы одна из двух фишек, стоящих на одной вертикали, должна сделать горизонтальный ход (иначе им не разминуться). Поэтому вместе эти фишки сделают не менее 15 ходов. А таких пар на доске восемь. Значит, менее чем за 120 ходов добиться требуемой расстановки нельзя.

Придумаем алгоритм. Разобьём фишки на четвёрки, стоящих на двух соседних вертикалях. Каждую четвёрку передвинем за 30 ходов так, как показано на рисунке:

"Потери"на горизонтальные ходы происходят только на втором и четвёртом этапах.