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

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

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

Рассмотрим левый квадрат на рисунке ниже:

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

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

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

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

Предположим, что Барон прав.

Рассмотрим произвольный прямоугольник со сторонами и . Тогда . Поскольку не больше 1 , то и , откуда Тогда площадь этого прямоугольника

Откуда мы сможем разместить внутри единичного квадрата не более 16 прямоугольников.

Противоречие.

Разобьем доску на рамки толщины и пронумеруем рамки по убыванию длин сторон. Тогда всего клеток в рамках с нечетными номерами

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

Пример для доски изображен на картинке и естественным образом обобщается на любое нечетное число.

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

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

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

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

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

с другой,

поскольку каждому ребру первого типа соответствует ровно один, а каждому ребру второго типа соответствует ровно два уникальных квадрата, общее количество которых равно .

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

Наконец,

следовательно,

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Периметр изначального квадрата равен см. Отрезав 2 прямоугольника, Аня увеличила периметр фигуры на 4 бОльшие стороны прямоугольника, а именно на см. БОльшая сторона прямоугольника равна см.

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

Подсчитаем, сколько раз в сумме всех периметров повторяется сторона исходного квадрата. Стороны прямоугольника считаютея по одному разу (итого 12), перемычки — по два раза ( ). Итого см — сторона квадрата.

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

С другой стороны, легко видеть, что внутрь квадрата фигура помещается целиком.

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

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

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

Получаем, что любая граница между разными цветами должна идти от края до края таблицы, причём с каждой стороны от неё будет одноцветная полоса клеток. Но это означает, что вертикальная и горизонтальная границы одновременно существовать не могут. Следовательно, либо все границы горизонтальные, либо все границы вертикальные, и раскраска в любом случае «полосатая». (Ширина каждой полосы при этом должна быть не менее 2 клеток - впрочем, для решения это значения не имеет.)

Это означает, что либо количества клеток каждого цвета делятся на высоту таблицы, либо на её ширину, как и разность . С другой стороны, эта разность не может быть равна 0 , так как в этом случае и общее количество клеток равно , но на 3 число не делится. Значит, или .

Равенство возможно, если красные клетки занимают 12 столбцов (по 28 клеток), розовые столько же, а синие - 11 столбцов. Если столбцы одного цвета расположить подряд, то все условия задачи будут выполнены.

Сначала рассмотрим “крайнюю” ситуацию. Если во всех клетках таблицы числа равны то и все произведения равны а их общая сумма равна

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Мы всегда считаем, что площадь торта равна

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

Осталось доказать, что детей всегда смогут получить желаемое. Пусть

— длины сторон кусков, которые хотят получить дети, то есть

Покажем, что из квадрата можно вырезать куски со сторонами

Для этого нам потребуются неравенства

Для доказательства первого неравенства заметим, что

в последнем переходе мы воспользовались неравенством между средним квадратичным и средним арифметическим. Второе неравенство доказывается аналогично:

Из неравенств следует, что можно разрезать торт на горизонтальные полосы высот, не меньших и соответственно, и в -ю полосу уложить квадраты со сторонами и как показано на рисунке ниже.

Оценка.

Покажем, что ходов обязательно придётся сделать.

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

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

Пример.

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

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

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

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

Теперь построим пример, доказывающий, что следовательно неравенство при неверно при всех достаточно больших

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

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

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

Пример.

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

Оценка

Первый способ.

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

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

Второй способ.

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

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

синих спичек.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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