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

Впишем в каждую белую клетку число 1, а в каждую чёрную — Пусть — сумма чисел, стоящих в -й строке, — сумма чисел, стоящих в -м столбце, — число, стоящее на пересечении этих строки и столбца.

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

Наконец,

Таким образом, все суммы и равны нулю.

Предположим противное: пусть среди четырёх клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета.

Назовём горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовём горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток:

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Давайте думать о клетках, как о вершинах графа. Ребра будут общими сторонами, а если есть перегородка, то ребро убираем. Хорошим лабиринтам соответствует связный граф. Заметим, что в связном графе на вершинах должно быть хотя бы ребра. А значит, хороший лабиринт содержит не более перегородок. Давайте рассмотрим какой-нибудь лабиринт и определим для него инвертированный лабиринт, то есть в нашем графе мы убираем ребра и добавляем ребра, которых не было. Тогда мы получаем соответствие лабиринтов с перегородками лабиринтам с перегородками. То есть каждому хорошему лабиринту мы точно сопоставили плохой. А у нас точно еще есть плохие лабиринты, поэтому плохих лабиринтов точно больше.

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

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

Ясно, что когда Дед Мороз красит 3-ю клетку (после этого хода 3 красные и 2 синие), Снегурочка закрасила только 2 клетки, а, значит, не могла выиграть. Покажем, что Дед Мороз может гарантировать себе победу.

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

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