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

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

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

Семи фигур не хватит, поскольку Пример для фигур легко строится: двумя такими фигурками легко покрыть квадрат а квадрат состоит из четырёх квадратов

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

Например, так:

Приведем пример. Паша мог расставить ладьи так:

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

Пример разрезания приведен на картинке. Возможно, он не единственный.

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

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

Теперь сделаем то же самое с первым и четвертым столбцом (2 хода), а потом - с первой и четвертой строкой (еще 2 хода).

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

Приведем пример, что оба варианта могут реализоваться.

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

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

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

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

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

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

Первые позиции заполняем различными простыми числами Эти числа должны быть новыми, то есть не использовавшимися ранее в таблице.

В следующих клетках размещаем числа

Последние две позиции оставляем незаполненными.

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

Это количество можно посчитать как разность количества клеток в квадрате и количества клеток в квадрате (размер пустого квадрата в рамке). Это равно .

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

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

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

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

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

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

вхождений Следовательно, имеем

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

В результате двойного подсчета мы получаем следовательно кратно Следовательно, должно быть кратно что завершает доказательство.

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

Пример разрезания на 9 многоугольников (для светлой темы):

Здесь 8 многоугольников с 1 чёрной клеткой и 3 белыми, оставшийся многоугольник содержит 17 чёрных клеток и 51 белую.

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

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

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

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

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

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