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

Предположим противное: пусть среди четырёх клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета.

Назовём горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовём горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток:

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

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

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

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

Пример. Черные клетки шахматной раскраски сделаем минами, а белые оставим пустыми.

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

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

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

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

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

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

Предположим противное. Ясно, что в таблице есть пустые столбцы. Заметим, что крайним пустой столбец быть не может. Действительно, если, скажем, правый столбец пуст, то из самого правого непустого столбца можно сдвинуть фишку вправо. Аналогично доказывается, что не может быть двух пустых столбцов подряд. Итак, слева от каждого пустого столбца есть фишка. Её нельзя сдвинуть вправо, значит, в той же строке справа через одну от неё стоит фишка. Таким образом, каждая “левая” фишка находится в строке, где есть другие фишки. Пусть всего пустых столбцов Тогда соответствующих “левых” фишек не меньше Следовательно, все фишки занимают не более строк, и пустых строк не меньше то есть больше чем пустых столбцов. Аналогично можно доказать, что пустых столбцов больше, чем пустых строк. Противоречие.

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

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

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

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

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

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

Пронумеруем столбцы прямоугольника слева направо, начиная с 1.

Заметим, что белый конь ходит только по нечётным столбцам и он будет оказываться в верхней клетке тогда и только тогда, когда номер столбца даёт остаток 1 при делении на 4, а в нижней — остаток 3. Но чёрный конь ходит по такому же принципу, как и белый, следовательно, наступит момент, когда белый конь находится в нижней клетке столбца, а чёрный конь — в верхней клетке столбца, и тогда кони не смогут сделать ходы, значит, они не смогут поменяться местами.

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

Давайте обозначим Для решения достаточно показать, что (1) Гриша всегда сможет набрать сумму больше и (2) Яша может расставить числа так, чтобы Гриша не смог набрать сумму больше

(1) Раскрасим клетки в черный и белый цвет в шахматном порядке. Сумма всех чисел нечетна, поэтому сумма чисел в клетках какого-то цвета будет больше — тогда Грише достаточно выбрать все клетки этого цвета.

(2) Разобьем доску на квадрат и каёмку толщиной в клетку. Далее разобьем квадрат на квадраты а каёмку — на прямоугольники один прямоугольник и один прямоугольник Разобьем множество на подмножества: и четверки и т. д.,

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

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

В прямоугольник поставим тройку ( в середине); тогда Гриша из клеток этого прямоугольника наберет не более то есть не более полусуммы чисел в этом прямоугольнике.

Наконец, в прямоугольник поставим числа и Суммируя по всем прямоугольникам разбиения, видим, что общая сумма Гриши не прeвысит

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Остаток при делении на не равен 0, поэтому мы не можем полностью покрыть доску клетками.

Следовательно, шахматную доску нельзя разрезать на уголки из трёх клеток.

Сложив суммы трех столбцов, получим, что сумма всех записанных чисел равна 333. Сложим теперь все ряды, проходящие через центр. Их 4: строка, столбец и две диагонали. Сумма равна 444. В нее центральное число входит четырежды, а остальные — ровно по разу. Три экземпляра центрального числа и дают избыток в 444 — 333 = 111. Значит, центральное число равно 111:3 = 37.

Найдем площадь прямоугольника:

Обе стороны прямоугольника должны быть не меньше 9, так как присутствует квадрат со стороной 9. Тогда единственный вариант разложения числа 464 на 2 множителя: Периметр прямоугольника в это случае будет равен 90.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

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

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

В решении будем называть квадратами все четверки с координатами Аналогичное определение введем для квадратов

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

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

откуда то есть

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

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