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

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

Замечание. Также можно заметить, что T-тетрамино не могут покрывать поровну черных и белых клеток, что тоже ведет к противоречию.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

______________________________________________________________________________________________________________________________________________________

Третье решение.

Разделим доску на квадраты размером и раскрасим их в черно-белые цвета в шахматном порядке:

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

_________________________________________________________________________________________________________________________________________________________________________________

Четвёртое решение.

Предположим противное и покрасим доску диагонально в цвета:

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

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

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

Разобьем доску на вертикальные полоски: левая и правая полоски будут иметь размеры , остальные — . Каждая из полосок легко бьется на прямоугольники , откуда и получается искомое разрезание.

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

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

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

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

Возможный пример разрезания указан на рисунке.

Как до него догадаться? Предварительно можно посчитать, что от квадратика остается клеток, и раз надо разрезать на фигур, то каждая фигурка состоит из клеток. А так как фигурки не должны являться прямоугольниками, то остается только уголок из трех клеток, и как раз на эти уголки мы и режем.

Сначала подумаем, что же будет полным решением этой задачи? Надо, во-первых, разбить два квадрата на две части. Кроме этого, надо также показать, как из 4 частей сложить квадрат . Это мы в итоге и сделаем, но сначала пару слов о том, как придумать такой пример.

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

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

В итоге квадрат мы сможем сложить так:

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

Пример такого разрезания указан на рисунке.

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

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

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

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

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

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

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

Нарисуем квадратную доску размеров на и раскрасим, как указано в условии.

Несложно видеть, что на этой картинке белых клеток.

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

Сопоставим многоугольнику граф: вершины - клетки, ребра будем проводить между соседними клетками. У каждой клетки 4 стороны, но стороны, которые соприкасаются с соседними клетками в многоугольнике, не учитываются в периметре. Значит, не учитываются те и только те стороны клеток, которым соответствуют ребра в графе (две стороны между соседними клетками соответствуют одному ребру). Граф на вершинах связен (так как у нас связная фигура), следовательно, ребер в нем хотя бы Значит, периметр многоугольника не больше Такой периметр достигается в прямоугольнике

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

Оценку можно доказать по-другому. По формуле Пика площадь многоугольника равна , где количество узлов сетки внутри многоугольника, количество узлов сетки на его границе. Поскольку контур многоугольника идет по линиям сетки, то его периметр равен количеству узлов сетки, то есть . Поскольку , то

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

Зафиксируем все квадраты со стороной положением их левого нижнего угла.

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

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

Итак, всего квадратов:

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

Получаем ответ

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

Поэтому остаток от деления на 5 суммы всех расставленных чисел равен

С другой стороны, в каждой полоске сумма чисел кратна пяти, а в квадрате сумма чисел равна Значит, остаток от деления на 5 суммы всех расставленных чисел равен 1 , и мы получаем противоречие.

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

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

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

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

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

Аналогичную оценку можно получить для суммы "вертикальных"слагаемых, что даёт нам итоговое значение 234.

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

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

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

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

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

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

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