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

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

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

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

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

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

Если или — нечётно, то в этих столбцах нет ни одного коротышки, расстояния от которого до двух выделенных домов одинаковы.

Если а чётно, то в столбце находится один коротышка, расстояния от которого до двух домов одинаковы.

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

Если же то в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно Аналогично, в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно

Заметим, что

Значит, какое-то из чисел не больше

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

Оценка:

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

Разобьем доску x на таких прямоугольников x В каждом из них нужно закрасить минимум клетки, тогда всего на доске нужно закрасить хотя бы клеток.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Итого

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

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

Нужно проверить, что клетка цвета в последней строке не окажется под боем клетки цвета в первой строке. Пусть — номер строки, больший 1, тогда клетка цвета в этой строке стоит в столбце. Значит, в последней строке клетка цвета стоит в столбце (1).

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

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

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

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

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

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

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

В обоих случаях найдется принцесса, которая будет побита.

Тогда если разбить доску на непересекающиеся области размера получим, что принцесс не более

48 принцесс разместить уже возможно:

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

Отсюда получаем уравнение

Периметр квадрата равен .

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

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

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

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

Для каждой ячейки посчитаем сумму чисел ней и в её соседях и сложим все эти суммы. Полученное число будет не менее

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

Чтобы достигалось равенство, необходимо, чтобы, во-первых, достигалось равенство в условии задачи, и, во-вторых, каждое ненулевое число суммировалось бы ровно семь раз, то есть, в каждой ячейке, у которой меньше семи соседей, стояло бы число

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

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

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

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

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

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

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

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

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

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

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

Если он затрагивает одну горизонталь, то в нём не более 14 отмеченных клеток.

Если он задевает 2 горизонтали (одна из них — вторая), то он задевает вертикаль с номером 7 (иначе в нём не более 14 клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные — чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.

Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно 3 (если он не задевает 7-й вертикали), либо имеет остаток 1 при делении на 3 (иначе).

В каждом из случаев получаем противоречие.

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

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

Разрежем доску так, как показано на рис. 1. Вырезанные из доски клетки при разрезании “испортят” не более 10 прямоугольников. Следовательно, у нас уже есть по крайней мере 22 целых прямоугольника. Покажем, как увеличить количество целых прямоугольников на 1. Рассмотрим изображённую на рис. 1 замкнутую цепочку клеток (по цепи идём от клетки а2 вверх). Поскольку вырезаны как белые, так и чёрные клетки, в этой цепи обязательно есть вырезанная белая клетка, за которой идёт вырезанная чёрная клетка.

Если эти клетки соседние, то они “портят” только один прямоугольник, значит, при таком разрезании будет не менее 23 целых прямоугольников.

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

Поделим клетки на три вида — угловые(4), боковые(12), внутренние(9). Легко видеть, что угловые входят ровно в один квадрат , боковые — в два, а внутренние — в 4. Чтобы сделать сумму по квадратам минимальной (а мы вдруг захотели сделать именно так), нужно взять первые два вида клеток, в сумме их как раз . Тогда сумма будет равна , чему она и равна по условию. Но поскольку это единственный способ получить такую сумму, то раскрашены могут быть только все клетки, кроме внутренних.

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

Пусть , где — длины сторон прямоугольника, тогда , действительно, если это не так, то

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

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

Пример на фишки: