Клетчатые задачи → .01 Раскраски

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

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

Замечание. Анализ поведения функции может быть проведён с использованием производной. Из того факта, что наибольшее значение функции достигается в точке , не следует вывод о том, что функция (по целым ) должна достигать наибольшего значения в одной из ближайших к целых точек. Хотя это верно для нашей функции, в общем случае существует контрпример. Для верного вывода нужна ссылка на монотонность.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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