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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

Если Первый сумеет сделать четыре хода, то он покроет какие-то 4 закрашенные клетки. Чтобы не дать Первому сделать пятый ход, Второй каждый свой ход также будет покрывать какую-то серую клетку, а если в какой-то момент Второй не сможет положить полоску ни на какую закрашенную клетку, то и Первый не сможет положить полоску ни на какую закрашенную клетку, и игра закончится раньше. Значит, Второй может помешать Первому сделать 5 и более ходов.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем, что Первый сможет выложить четыре полоски . Рассмотрим первые два хода Первого.

Пусть Первый своим первым ходом положил полоску на место прямоугольника 1:

После этого при любом своём ходе Второй не сможет положить полоску так, чтобы она налегала и на прямоугольник 2 , и на прямоугольник 3 . Значит, Первый своим вторым ходом сможет положить полоску либо на прямоугольник 2 , либо на прямоугольник 3. Без ограничения общности, пусть он смог положить полоску на прямоугольник 2. Затем Второй сделает свой второй ход. Поделим доску на области (a), (б), (в):

и рассмотрим все возможные варианты первых двух ходов Второго.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Если — четное число, то вся таблица разбивается на квадратов , в каждом из которых находится ровно 2 фишки. Поэтому общее число фишек равно .

Пусть теперь . Разобьем таблицу на квадраты и фигуры вида:

так, как показано на рисунке:

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

Таким образом, общее число фишек в таблице не менее

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

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

(В этом примере число фишек равно , где .

Выделим четыре квадрата , примыкающие к углам квадрата :

Эти квадраты не пересекаются, поэтому если закрашено не более трех клеток, то хотя бы один из этих квадратов остался целиком белым. Если же мы закрасим 4 клетки, отмеченные на рисунке серым, то ни одного белого квадрата не останется.

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

Оценка:

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Итого

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

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

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

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

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

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 целых прямоугольников.

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

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

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

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

Пример для показан на рисунке.

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

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

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

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

Разобьем таблицу на четыре квадрата суммы в них обозначим за

Заметим, что

Это означает, что одно из чисел или по модулю превосходит Но в каждом из соответствующих квадратов всего клеток, и числа в них по модулю не превосходят Противоречие.

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

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

Пример с таким количеством отмеченных клеток показан на рис. справа.

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

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

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