Раскраски

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

Раскрасим клетки второй, четвёртой и шестой строки в чёрный цвет. Заметим, что в одну букву Г входит либо одна, либо три чёрные клетки, то есть нечётное количество. Предположим, что разрезать можно. Всего будет фигур, то есть всего на доске нечётное количество (сумма нечётного количества нечётных чисел нечётна) чёрных клеток. Однако всего чёрных клеток, противоречие.

Пусть вырезан левый нижний уголок (не умаляя общности). Раскрасим клетки в чёрный цвет как показано на рисунке:

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

Замечание. Текст решения ниже написан с ориентиром на белую тему. В тёмной теме цвета надо поменять местами.

_________________________________________________________________________________________________________________________________________________________________________________

Раскрасим чёрным цветом клетки как показано на картинке:

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

А теперь покрасим в чёрный клетки по-другому:

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

Осталось привести пример:

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

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

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

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

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

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

Получаем, что любая граница между разными цветами должна идти от края до края таблицы, причём с каждой стороны от неё будет одноцветная полоса клеток. Но это означает, что вертикальная и горизонтальная границы одновременно существовать не могут. Следовательно, либо все границы горизонтальные, либо все границы вертикальные, и раскраска в любом случае «полосатая». (Ширина каждой полосы при этом должна быть не менее 2 клеток - впрочем, для решения это значения не имеет.)

Это означает, что либо количества клеток каждого цвета делятся на высоту таблицы, либо на её ширину, как и разность . С другой стороны, эта разность не может быть равна 0 , так как в этом случае и общее количество клеток равно , но на 3 число не делится. Значит, или .

Равенство возможно, если красные клетки занимают 12 столбцов (по 28 клеток), розовые столько же, а синие - 11 столбцов. Если столбцы одного цвета расположить подряд, то все условия задачи будут выполнены.

Оценка.

Покажем, что ходов обязательно придётся сделать.

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

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

Пример.

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

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

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

Пример.

Пронумеруем спичечные столбцы и строчки таблицы от 1 до . Сначала уберём все спички на границе. Затем уберём по 2 верхние спички 2 -го, 4 -го, . . -го столбцов. Затем во 2 -й строчке уберём спичек ( отрезок длины 2 ) так, чтобы остались спички по краям. Затем уберём по 2 спички из 3 -го, 5 -го, ..., -го столбцов так, чтобы сверху осталось по одной спичке в этих столбцах. Далее уберём все спички 3 -й строчки. Затем уберём по 2 верхние спички чётных столбцов, затем средних спичек 4 -й строчки, затем верхние спички внечётных столбцах, а затем все спички 5-й строки. Будем дальше продолжать этот алгоритм, несложно убедиться, что останутся только крайние спички в нечётных столбцах (не считая 1 и ) и чётных строках, в итоге .

Оценка

Первый способ.

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

Таким образом, в конце останется хотя бы по одной покрашенной спичке в каждом из выделенных квадратиков.

Второй способ.

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

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

синих спичек.

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

Нужно проверить, что клетка цвета в последней строке не окажется под боем клетки цвета в первой строке. Пусть — номер строки, больший 1, тогда клетка цвета в этой строке стоит в столбце. Значит, в последней строке клетка цвета стоит в столбце (1).

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

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

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

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

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

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

Приведём пример заполнения клеток таблицы и порядка обхода этих клеток кузнечиком (см. рисунок В клетках стоят единицы, во всех остальных — тройки. Порядок обхода по возрастанию индексов.

Пусть , где — длины сторон прямоугольника, тогда , действительно, если это не так, то

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

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

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

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

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

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

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

Пример подходящей расстановки:

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

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

Пример приведен на картинке, клетки пронумерованы в порядке обхода клона, клетка с номером один — та, с которой он начинает.

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

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