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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Оценка. Разобьём квадрат на квадратиков

Среди этих квадратиков не более

квадратиков, в которых покрашено хотя бы 2 клетки.
Остальных квадратиков — не менее

Из каждого из них можно вырезать трёхклеточный уголок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что в каждой вертикали и каждой горизонтали стоит ровно по одной ладье.

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

Пусть для определённости и лежат в части I. Тогда все граничные клетки между ними также должны лежать в части I; действительно, если какая-то такая клетка лежит в части II, то в ней же лежит какой-то путь из в а в части I лежит какой-то путь из в но эти пути должны иметь общую клетку, что невозможно.

Значит, вся горизонталь между клетками и лежит в части I, то есть в ней должна быть хотя бы одна ладья. Аналогично, в части II тоже есть целая горизонталь (между и ), а значит, есть ладья. Отсюда и следует требуемое.

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

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

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

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

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

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

Оценка. Отметим 25 клеток доски , как показано на рисунке:

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

Пример. Составим из 50 квадратиков два квадрата . Один положим в левый нижний угол доски , а другой — в правый верхний угол.

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

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

Пример. На рисунке снизу показан пример для (при других чётных примеры аналогичны).

Посчитаем количество пустых клеток

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

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

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

Приведём пример на нанесём удар по отмеченным клеткам:

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

Осталось привести пример, поставив королей на отмеченные клетки:

Разобьём доску на фигурки следующим образом:

В трёхклеточных уголках и квадратах может быть не более двух закрашенных клеток.

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

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

Заметим, что в каждом квадратике должно быть выделено хотя бы 2 клетки. Так как все кроме крайнего столбика можно разделить на квадратики, то отмеченных клеток должно быть хотя бы

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