Клетчатые задачи → .02 Разбиение доски на части

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. На клетчатой плоскости закрашено клеток. Тогда есть не более квадратов содержащих хотя бы две отмеченные клетки.

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

База. Все клеток в одной строке. Если они стоят подряд, то есть в точности квадратов. А если не подряд, то ещё меньше.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Сначала приведём стратегию за Соню. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов Получается, что какие-то две монеты лежат в одном и том же квадрате Если эти две монеты соседние по стороне, то Соня надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше 300.

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

Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца в соседний столбец. Тогда Даша своим ходом вернёт её в столбец Таким образом, на доске всегда останется хотя бы 100 монет, и Соня заработает не более трёхсот рублей.

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

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

1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — черным, пятый столбец — белым, и далее продолжаем с периодом 5.

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

Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник Далее продолжим аналогичные рассуждения с отрезанием прямоугольников Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и 5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено.

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

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

Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3 клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее

Но оно равно 100. Отсюда и что невозможно при Неравенство установлено. Доказательство оценки завершено.

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

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

Разобьём квадрат на прямоугольника Так как вырезанных клеток то из одного такого прямоугольника вырезано не более одной клетки. Из него и можно получить необходимую 4-клеточную фигурку в виде буквы “Г”.

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

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

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

Рассмотрим в нашем квадрате квадратов

Назовём их выделенными.

Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату.

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

Получаем оценку: максимальное число непересекающихся диполей во всём квадрате не больше

Построим теперь пример на диполей. Для этого “отрежем” левый нижний выделенный квадрат. Останется клетчатая фигура из клеток, которая разбивается на квадрат и два прямоугольника и Эта фигура полностью разбивается на диполи, поскольку любые последовательные клеток строки или столбца, очевидно, разбиваются на три диполя.

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

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

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

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

хороших клеток уже возможно.

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

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

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

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

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

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

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

Давайте обозначим Для решения достаточно показать, что (1) Гриша всегда сможет набрать сумму больше и (2) Яша может расставить числа так, чтобы Гриша не смог набрать сумму больше

(1) Раскрасим клетки в черный и белый цвет в шахматном порядке. Сумма всех чисел нечетна, поэтому сумма чисел в клетках какого-то цвета будет больше — тогда Грише достаточно выбрать все клетки этого цвета.

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

В каждый квадрат мы поставим четверку чисел чтобы и стояли на одной диагонали, а и — на другой; тогда в любом случае Гриша из клеток этого квадрата наберет не более полусуммы чисел в этом квадрате.

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

В прямоугольник поставим тройку ( в середине); тогда Гриша из клеток этого прямоугольника наберет не более то есть не более полусуммы чисел в этом прямоугольнике.

Наконец, в прямоугольник поставим числа и Суммируя по всем прямоугольникам разбиения, видим, что общая сумма Гриши не прeвысит

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Замечание. Нам даются условия на квадраты и на бесконечной клетчатой доске. Чтобы привести условия к одному виду, переформулируем их в терминах квадратов Легко видеть, что произвольный квадрат можно разбить на непересекающихся квадратов или на непересекающихся квадратов

Первое решение.

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

Второе решение.

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

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