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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: Покрасим все строки доски с нечётными номерами ( клетки). Любой уголок содержит клетки двух каких-то соседних строк, потому в нём будут закрашенные.