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

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

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

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

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

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

Пусть у Нюши прямоугольник имеет размеры , а у Бараша — . Сравниваем периметры:

А если сравнить площади, то

то есть два таких прямоугольника подходят под условие.

Комментарий. Разумеется, для полного решения этой задачи достаточно привести любой пример, коих множество. Не смущайтесь, что у Бараша в данном примере квадрат — квадрат тоже является прямоугольником.

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

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

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

В этой задачке раскраска уже не дает противоречия. Давайте просто оценим количество ходов, которое нужно ладье, чтобы попасть в центральную клетку из угловой. Ей нужно сделать минимум 55 ходов по горизонтали и столько же по вертикали, то есть в сумме хотя бы 110 ходов. Но она сделала только 88 — поэтому дойти до центральной клетки не может.

Заметим, что чётные и нечётные клетки на пути Лизы чередуются: из нечётной клетки Лиза всегда прыгает в чётную, а из чётной — в нечётную. При этом начинала Лиза с нечётной клетки, а закончила в чётной. Это значит, что на нечётных клетках Лиза побывала столько же раз, сколько на чётных. В нечётных клетках Лиза побывала раз. В чётных раз, где  — количество раз, которое Лиза была в клетке номер 10. Тогда .

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

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

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

Рассмотрим разрезание как на картинке. Четыре прямоугольника на границе имеют размер . Оставшиеся 19 прямоугольников имеют размер .

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

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

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

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

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

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

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

Расстановок, когда -я фигура бьёт -ю — не более чем

Умножив на число пар получим грубую оценку сверху количества “плохих” расстановок:

Но это число меньше чем количество всех расстановок. (

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

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

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

Теперь осталось придумать пример на 91.

Раскрасим доску в шахматном порядке.

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

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

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